소수 알고리즘

기본 알고리즘

count=78022 

가장 기본적인 소수 판별 알고리즘이다. 무식하게 2부터 i까지 반복하여 소수를 판별한다.

시간복잡도가 매우 크다.

 

n=1000
count=0
for i in range(2,1001):
 for j in range(2,i):
  count+=1
  if i%j==0:
   break
  else:
  print(i)
print(count)

 

배열을 사용한 알고리즘

count = 14622

배열을 선언, 2는 소수이므로 prime[0]에 2를 저장하고 ptr을 1증가시킨다.

4이상의 짝수는 소수가 아니므로 2를 3부터 2를 증가시켜 반복한다.

ptr의 수만큼 반복한다. ptr은 1로 else로 넘어가 prime[1]에 3을 누적한다.

이렇게 반복하여 소수의 수를 이용하여 소수를 판별하여 시간복잡도를 줄인다.

하지만 메모리 초과를 주의해야한다.

 

count=0
ptr=0
prime=[None]*500

prime[ptr]=2
ptr+=1

for n in range(3,1001,2):
 for i in range(1,ptr):
  count+=1
  if n% prime[i]==0:
   break
 else:
  prime[ptr]=n
ptr+=1

for i in range(ptr):
 print(prime[i])
 print(count)

 

에라토스테네스의 체

   count=3000

   모든 약수는 가운데 약수를 기준으로 대칭을 이룬다.
   ex) 16 => 1 2 4 8 16 이다,
   1*16 , 2*8, 4*4 로  약수를 찾을 때는 가운데 약수 즉 제곱근까지 확인하면 된다.

 

1. 2부터 n까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은수 i 를 찾는다.
3. 남은 수 중 i의 배수를 모두 제거한다.
4. 더이상 반복할 수 없을때까지 2번과 3번의 과정을 반복

 

즉 에라토스테네스의 체는 2부터 n까지의 수 중 소수를 판별하고 그 수가 소수이면 그 수에 해당하는 배수를 모두 지운다. 이 과정을 제곱근 n번 반복하고 나머지 수를 구한다. 이 나머지 수가 바로 소수이다.

 *제곱근- import math -> math.sqrt(수)

 

import math
n=1000
count=0
arr=[True for i in range(n+1)]

for i in range(2, int(math.sqrt(n)+1)):
 if arr[i]==True:
  j=2
 while i*j<=n:
   count+=2
   arr[i*j]=False
   j+=1

for i in range(2,n+1):
 if arr[i]:
  print(i)
print(count)