python 소수의 판별

소수(prime_number)란 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수이다

가장 기본적인 소수판별 함수

def is_prime_number(x):
    for i in range(2,x): #ex) x가 4이면 2~3까지 반복한다 마지막 인덱스 -1 까찌만 반복한다
      if x % i == 0:
        return False
    return True 

print(is_prime_number(4))  #false

제곱근을 활용한 소수의 판별

자연수의 약수가 가지는 특징은 가운데 약수를 기준으로 해서 각 등식이 대칭적인 형태를 보인다.

우리는 특정한 자연수 X가 소수인지 확인하기 위하여 바로 가운데 약수까지만 나누어 떨어지는지 확인하면된다

import math

def is_prime_number(x):
  for i in range(2,int(math.sqrt(x))+1): # ex)  x가 4일경우 int(math.squrt(4)) ==2 
    if x % i ==0:
      return False
  return True
print(is_prime_number(4)) #False

에라토스테네스의 체

여러 개의 수가 소수인지 아닌지를 판별할 떄 사용하는 대표적인 알고리즘

N보다 작거나 같은 모든 소수를 찾을 떄 사용할 수 있다.

메모리가 많이 필요하다는 단점이 동반 (N의 크기기 만큼 리스트를 할당하고 사용해야 하기 때문에

import math

n=10

array=[True for i in range(n+1)] #0~10

for i in range(2,int(math.sqrt(n))+1): # 범위가 2인 이유 1은 소수가 아니다 
  j=2
  while i*j<=n+1:
    array[i*j] = False
    j+=1

for i in range(2,n):
  if(array[i]):
    print(i,end=' ') # 2 3 5 7   end = ' ' 공백 한 칸 지정
# print 의 end 에 빈문자열을 넣을 경우 한줄에 여러개의 값을 받을 수 있다.