section2.7 소수(에라토스테네스 체)

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요. 만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다. 제한시간은 1초입니다.

 

 

 

import sys
sys.stdin = open("input.txt", "rt")
n = int(input())

for x in range(3, n+1):
    for y in range(2, x):
        if x%y == 0:
            break

 

 

소수 > 다른 숫자로 나눴을 때 무조건 나머지가 남음

이 점을 이용해서 for 문에서 나머지가 없으면 그 순간 break이고 break가 한 번도 안 걸린 경우 소수로 생각했다

문제는 9와 같이 2에서는 나머지가 안 남지만 3에서 break가 되는 경우였다

for ~ else 구문을 사용했으면 내가 생각한대로 구현할 수 있었을 것 같다

 

아니면 input값을 받고 리스트를 만든 다음에 소수가 아니면 pop 하는 방법도 가능할 것 같다

 

 

import sys
sys.stdin = open("input.txt", "rt")
n = int(input())
ch = [0]*(n+1)
cnt = 0

for i in range(2, n+1):
    if ch[i] == 0:
        cnt += 1
        for j in range(i, n+1, i):
            ch[j] = 1
print(cnt)

 

정답은 이런식으로 ch 리스트를 만든 후 채워나가는 것이었는데 신박하다 

 

 

 

for - else문 정리

for i in range(5):
	if i == 2:
    	break
    print(i, end=' ')
else:
	print("for문 끝")

출력값 : 0 1 

for문이 break 등으로 중간에 빠져나오지 않고 끝까지 실행됐을 경우 else문이 실행되는 방식

 

 

import sys
sys.stdin = open("input.txt", "rt")
n = int(input())
cnt = 0

for x in range(3, n+1):
    for y in range(2, x):
        if x%y == 0:
            break
    else: 
        print(x, y, x%y)
        cnt += 1
print(cnt+1)

for-else문을 활용해서 다시 답을 만들었다

이중 for문에서 2를 어떻게 할 수가 없어서 어차피 항상 소수이니까 마지막 cnt에 1을 더해줬다.