파이썬(python) 알고리즘 - 소수 찾기

소수 판별, 소수 찾기, 소수 검사, 소수 판단

특정 숫자의 약수들을 나열했을때의 중앙값 <= 루트(n) 이라는 아이디어 사용

1부터 루트(n) 까지의 값으로 나눠서 0이면 소수로 판별.

4 : 1 2 4 
루트(4) = 2

10 : 1 2 5 10
루트(10) = 3.XX

 

소수 검사 함수

import sys
import math

def prime_check(n):
    if n == 1 :
        return False
    for div in range(2,int(math.sqrt(n))+1):
        if n%div == 0:
            return False
    return True

 

에라토스테네스의 체

매번 함수를 돌리자니 시간이 많이 걸림.

특정 범위에 대한 소수 여부를 미리 한번에 다 구해버리자는 아이디어

메모리 공간을 써서 시간을 줄이는 개념임.

 

0,1 은 소수 x

2 : 2제외, 2의 배수를 소수제외 → 4 6 8 10 12 14 16 ...

3 : 3제외, 3의 배수를 소수제외 → 9 12 15 18 21 24 ...

4 : pass

5 : 5제외. 5의 배수를 소수제외 → 5 10 15 20 25 ...

import sys
def prime_check(n):
    c = [False,False] + [True]*(n-1)
    for i in range(2, n+1):
        if c[i] == True:
            for j in range(2*i, n+1, i):
                c[j] = False
    return c

 

---

백준 1978 : 소수 찾기

1978번: 소수 찾기

단순히 for 문으로 풀기

import sys
import math

n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
prime = n
for number in numbers:
    if number == 1:
        prime-=1
        continue
    else:
        for div in range(2,int(math.sqrt(number))+1):
            if number%div == 0:
                prime-=1
                break
print(prime)

함수를 만들어서 호출하여 풀기

import sys
import math

def prime_check(n):
    if n == 1 :
        return False
    for div in range(2,int(math.sqrt(n))+1):
        if n%div == 0:
            return False
    return True

n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
sum = 0
for number in numbers:
    if prime_check(number):
        sum+=1
print(sum)

에라토스테네스의 체로 풀기

import sys
def prime_check(n):
    c = [False,False] + [True]*(n-1)
    for i in range(2, n+1):
        if c[i] == True:
            for j in range(2*i, n+1, i):
                c[j] = False
    return c
    
    
n = int(sys.stdin.readline())
numbers = map(int, sys.stdin.readline().split())
sum = 0
prime_list = prime_check(1000)
for number in numbers:
    if prime_list[number]:
        sum+=1
print(sum)