프로그래머스 레벨1의 소수 검사문제를 풀고나서 써본다.

소수 검사

n=100 #100까지의 소수 검사

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

for i in range(n+1):
  if isPrime(i) :
    print(i) # 소수 출력

• 0926) 제곱수까지 판별하면 실행시간이 훨씬 짧다.

에라토스테네스의 체

한 개의 소수를 구할 때는 그런대로 괜찮은 방법인데 범위의 모든 소수를 구할 때는 효율적인 방법이 아니다.

에라토스테네스의 체 : 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법.
1. 1은 제거
2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.
5. (반복)

n=1000 #1000까지의 소수 검사
a = [False,False] + [True]*(n-1) #0,1은 소수가 아님. 2부터 n까지의 수를 소수로 둠
primes=[] # 소수들

for i in range(2,n+1):
  if a[i]: #소수면
    primes.append(i) #소수 리스트에 추가
    for j in range(2*i, n+1, i): 
        a[j] = False #i의 2배수부터 끝까지, i만큼 뛰어넘으며 소수에서 탈락시킴
print(primes)

참고

https://wikidocs.net/21638