소수 구하기와 에라토스테네의 체

소수 구하기

def is_prime(x):
    for i in range(2, int(x ** 0.5) + 1):
        if(x % i == 0):
            return False
    return True

 

x값을 받으면 2부터 x의 제곱근까지 하나하나 x랑 나누어떨어지는지 확인을 해보고 나누어 떨어지면 소수가 아니므로

False 값을 반환하고 나누어 떨어지는게 없으면 소수이므로 True 값을 반환한다.

 

에라토스테네의 체

arr = [0,1] + [i for i in range(2,101)]

for i in range(2, int(100 ** 0.5) + 1):
    if(arr[i] == 0):
    	continue
    for j in range(i + i, 101, i):
    	arr[j] = 0

for i in range(2,len(arr)):
    if(arr[i] != 0):
    	print(arr[i],end=" ")

 

배열을 0 부터 100까지 초기화를 한다.

2부터 100까지 순서대로 약수인지 확인하고 만약 약수면 약수의 배수를 다 0으로 만들어서 지운다.

그렇게 반복을 끝내면 100이하의 소수만 남게 된다.

그리고 마지막으로 그것을 print를 해서 보여준다.