1978 소수 찾기

아이디어

최초의 아이디어 -> 2부터 N-1까지 나누기 (단순무식한 방법)

구현

단순무식한 방법으로 구현 (그래도 정답은 나옴)

def prime_checker(number):
    if number == 1:
        return False
    else:
        for i in range(2, number):  # 2부터 자기 자신-1 까지 나머지가 0이 나오면 제외
            if number % i == 0:
                return False
        return True


n = int(input())
numbers = list(map(int, input().split()))
prime_numbers = [number for number in numbers if prime_checker(number)]
print(len(prime_numbers))

또는

n = int(input())
nums = list(map(int,input().split()))
ans = []
for i in nums:
    if i == 1:
        continue
    for j in range(2, i-1):
        if i%j == 0:
            break
    else:
        ans.append(i)
print(len(ans))

그러나.. 이걸 골드바흐의 추측에 끌고갈경우 피를 보게 된다..

쬐끔 더 나은 방법

사실 N-1까지 갈 필요가 없다... N의 제곱근까지만 검사해보면 된다..

진짜 제대로 된 방법 (자료구조 책 참고)

자연수들이 아니라 "소수"로 나눌 것!!

def prime_list_maker(number):
    prime_list = [2]
    for i in range(3, number, 2):
        for prime in prime_list:
            if i % prime == 0:
                break
        else:
            prime_list.append(i)  # for 문 뒤의 else..
    return prime_list

(골드바흐 추측 풀 때 들어간 소수 리스트 만드는 버전)

1. 일단 소수 리스트(prime_list)에 미리 2를 넣은 상태로 초기화
2. 3부터 주어진 수 사이에 있는 홀수들에 대해 (당연히 짝수는 소수가 아니므로 검사할 필요 없음!!!)
3. 소수 리스트에 있는 소수들에 대해 나눠지는지 검사
4. 하나라도 나눠지면 break, 안 나눠지면 소수 리스트에 새로 추가

기억해야 할 파이썬 문법 : for 문 뒤의 else