[코터스] 엄청 큰 소수 판별

serotonins·2022년 10월 25일
0

Coding Q

목록 보기
12/17
n = int(input())

sosu = [i for i in range(int(n**0.5)+1)] # 나눠볼 수는 제곱근까지면 되니까
sosu[1]=0
out = 1

if n<2 or n%2==0: out = 0 # 짝수 패스
else: 
    for i in range(3, int(n**0.5)+1, 2): # 홀수만 알아보기
        if sosu[i] > 1: 
            if n%i==0: out=0; break;
            for j in range(i+i, int(n**0.5)+1, i): # for j in range(i*i, int(n**0.5)+1, 2*i):
                sosu[j] = 0

print(out) # 1이면 소수, 0이면 소수 아님

#붙은 저거 원리 알아보기

0개의 댓글