[백준] 1929번 (python 파이썬)

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

import sys

M, N = list(map(int,sys.stdin.readline().split()))
prime_number = [True] * N
prime_number[0] = False

i = 1
while i < len(prime_number):
  if prime_number[i]:
    j = (i+1)*2 -1
    while j < len(prime_number):
      prime_number[j] = False      
      j += (i+1)
  i += 1

for n in range(M, N+1):
  if prime_number[n-1]:
    print(n)

입력받은 수 중에 가장 큰 수를 기준으로 에라토스테네스의 체를 만든다.

그리고 소수인지 판별해서 출력한다.

위의 코드는 while문으로 반복수행 했고, 아래 코드는 for문으로 반복수행 했다.

import sys

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

prime_number = [True] * N
prime_number[0] = False

for i in range(1, len(prime_number)):
  if prime_number[i]:
    for j in range((i+1)*2-1, N, i+1):
      prime_number[j] = False      
      
for n in range(M, N+1):
  if prime_number[n-1]:
    print(n)

 

 

-> for문

 

-> while문

 

for문으로 작성한 코드가 코드 길이도 적을 뿐더러 시간이 빠르다.

 

거기에 합성수 n이  p*q로 표현될 때, 한 수는 항상 n^(1/2)이하, 다른 한 수는 n^(1/2) 이상이라는 점을 이용하면 n-1까지 순회하지 않고 n^(1/2)까지만 순회하도록 최적화할 수 있다.

import sys

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

prime_number = [True] * N
prime_number[0] = False

m = int(len(prime_number) ** 0.5)
for i in range(1, m + 1):
  if prime_number[i]:
    for j in range((i+1)*2-1, N, i+1):
      prime_number[j] = False      
      
for n in range(M, N+1):
  if prime_number[n-1]:
    print(n)

 

 

 

-> 최적화 코드