[백준 파이썬 1929번]소수 구하기★에라토스테네스의 체★VER3.0

VERSION 3.0

import sys
import math

M,N = list(map(int,sys.stdin.readline().split()))

a = [True for i in range(N+1)]


a[0],a[1] = False , False

for i in range(2, int(math.sqrt(N)+1)):

    j=2
    if a[i]== True:
        while True:
            if i*j> len(a)-1:
                break

            if a[i*j] == True:
                a[i*j]= False

            j+=1

for i in range(M,N+1):
    if a[i] == True:
        print(i)

==> True 일때 체크하기!!!

VERSION 2.0

 

import sys
import math
A = list(map(int, sys.stdin.readline().split()))
#print("A : {}".format(A))

def is_prime_number(n):
    array = []
    for i in range(n+1):
        array.append(True)
    #print("array_1 : {}".format(array))
    array[0] , array[1] = False, False
    for j in range(2 , int(math.sqrt(n))+1):
        #A[1] = 16
        #range(2,5)
        if array[j] == True:
            k =2
            while (j*k <= n):
                #2*2 < 16
                #array[4] =False
                #2*3 < 16
                #array[6] =False
                #.... array[16] =False

                #array[3] = True
                #array[6] =False
                #array[9] =False
                #array[12] =False
                #array[15] = False

                if array[j*k] == True:
                    array[j *k] = False
                k+=1
    return array
#print("array_2 : {}".format(array))
res = []
res_array = is_prime_number(A[1])
for i in range(A[0] , A[1]+1):
    if res_array[i] == True:
        res.append(i)
# print("res : {}".format(res))
for j in res:
    print(j)

VERSION 1.0

 

import math
import sys
# 소수 판별 함수(에라토스테네스의 체)
def is_prime_number(m, n):
    # 2부터 n까지의 모든 수에 대하여 소수 판별
    array=[]
    for i in range(n+1):
        array.append(True)
    array[1] , array[0] = False
    # 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외)
    # 에라토스테네스의 체
    for i in range(2, int(math.sqrt(n)) + 1): #2부터 n의 제곱근까지의 모든 수를 확인하며 ==> 루트 26 ==> 5.xxx ==int(5.xxxx) ==> 5 +1 = 6
        if array[i] == True: # i가 소수인 경우(남은 수인 경우)
            # i를 제외한 i의 모든 배수를 지우기
            j = 2
            while i * j <= n:

                array[i * j] = False
                j += 1
                #2*2 < 13:                2*2<5
                #array[4] = False         array[4] =False
                #j+=1 ==> j=3             j=3
                #2*3 < 13:
                #array[6] =False
                #j+=1 ==> j=4
                #2*4 < 13:
                #array[8] = False
                #2*5 < 10:
                #array[10] = False
                #j+=1 ==> j=5
                #2*6 < 12:
                #array[12] = False
                #j+=1 ==> j=6
                #2*7 < 14:
                #array[14] = False
                #j+=1 ==> j=7
                #array
    array2=[]
    for i in range(m, len(array)):

        if array[i] == True:
            array2.append(i)
    return array2


A = list(map(int, sys.stdin.readline().split()))
for i in is_prime_number(A[0],A[1]):
    print(i)