greentea31's Note

https://programmers.co.kr/learn/courses/30/lessons/42839

풀이 과정

numbers 문자열의 각 문자로 몇 개의 소수를 만들 수 있는지 반환해줘야 한다.

나올 수 있는 최대 수까지 에라토스테네스의 체를 사용해 소수를 미리 구해준 후, numbers의 각 문자로 만들 수 있는 모든 숫자의 쌍을 permutations 모듈을 이용하여 구해주었다. 그 후, 숫자가 소수면 정답 후보 리스트에 넣고, 정답 후보 리스트를 set으로 바꿔줬다가 list로 바꿔줘서 중복을 제거한 후, 리스트의 원소의 개수를 리턴하여 답을 구하였다.

소스 코드

from itertools import permutations


def solution(numbers):
    max_number = 10000001
    check = [False for _ in range(max_number)]
    check[0], check[1] = True, True
    
    for i in range(2, max_number):
        if not check[i]:
            for j in range(2*i, max_number, i):
                check[j] = True
                
    numbers = list(str(numbers))
    number_list = []
    
    for i in range(1, len(numbers) + 1):
        for j in permutations(numbers, i):
            temp = int(''.join(j))
            if not check[temp]:
                number_list.append(temp)
    
    return len(list(set(number_list)))

https://programmers.co.kr/learn/courses/30/lessons/12921

풀이 과정

일정 범위에 있는 모든 소수를 찾아야 하는 문제이다. 1부터 n까지의 수에 대해 모두 소수 판정을 하면서 개수를 세면 답이야 구해지겠지만 시간복잡도가 O(NrootN)인 방법이 되어 효율성 테스트를 통과할 수가 없다.

일정 범위에 있는 모든 소수를 찾아야 할 때는 에라토스테네스의 체를 사용하는게 효과적이다. 에라토스테네스의 체가 무엇인지 모르면 아래 위키백과를 참조하면 좋다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체의 시간복잡도는 O(NloglogN)으로 더 효율적이다 N이 100만이라 할때 일일이 소수 판정을 하면 연산 횟수가 약 10억번 언저리까지 나올 수 있지만 에라토스테네스의 체로는 2천만번 언저리의 연산으로 해결이 가능하다.

소스 코드

def solution(n):
    answer = 0
    check = [False for _ in range(1000001)]
    prime = [] 

    for i in range(2, 1000001):
        if not check[i]:
            prime.append(i)
            for j in range(2*i, 1000001, i):
                check[j] = True

    for prime_number in prime:
        if prime_number > n:
            break
        else:
            answer += 1

    return answer

https://www.acmicpc.net/problem/1978

풀이 과정

어떤 수 N이 소수임을 판정하려면 2부터 N-1까지 나누면서 나누어 떨어지는지 확인하면 된다.

=> 2부터 N/2까지만 나누어도 된다. N = a * b (2 <= a <= b <= N-1)에서 b는 N/2를 넘을 수 없다.

=> 2부터 rootN까지만 나누어도 된다. N = a * b (2 <= a <= b <= N-1) 에서 rootN 이하의 a를 발견하지 못했으면 b는 존재하지 않기 때문이다

이유: rootN 이상의 a가 존재하면 b = N / a인데 a가 rootN보다 크므로 b가 rootN보다 작게 된다. 근데 그러면 a <= b가 아니므로 존재할 수 없다.

따라서 2부터 rootN까지 나눠보면서 소수 판정을 진행하면 된다.

코드

import sys

N = int(sys.stdin.readline())
inPu = list(map(int, sys.stdin.readline().split()))
answer = 0
for i in inPu:
    if i == 1: continue
    primeFlag = True
    for K in range(2, int(i**(1/2)) + 1):
        if i % K == 0: primeFlag = False
    if primeFlag: answer += 1
    else: pass

print(answer)