Algorithm

[Python] 소수 찾기

KOOCCI 2019. 5. 23. 01:20

[참고 문제 : https://www.acmicpc.net/problem/1929 ]


문제 풀이

 

에라스토테네스의 체를 활용

2부터, 알고 싶은 값의 sqrt 값보다 작은 값까지를 범위로 하여, 해당 값이 나누어지는지 비교해보면, 소수 여부를 알 수 있다는 것이다.

 

import math

M, N = map(int, input().split())

arr = []

for i in range(M, N+1):
  if i != 1:
    flag = True
    for j in range(2, int(math.sqrt(i)) + 1):
      if i % j == 0:
        flag = False
        break
    if flag:
      print(i)

'Algorithm' 카테고리의 다른 글

[java] Rotate Array  (0) 2022.06.24
[java] Median of Two Sorted Arrays  (0) 2022.06.23
[java] Longest Substring Without Repeating Characters  (0) 2022.06.23
[java] jump game 2  (0) 2022.06.22
[Python / C++] 스택 수열  (0) 2019.05.23