자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.
만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.
제한시간은 1초입니다.
▣ 입력설명
첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.
▣ 출력설명
첫 줄에 소수의 개수를 출력합니다.
▣ 입력예제 1
20
▣ 출력예제 1
8
내가 푼 방법
먼저 하나의 숫자가 소수인지 아닌지 판별하는 코드
# 소수 판별 함수(2이상의 자연수에 대하여)
def is_prime_number(x):
if x==2 or x==3:
return True
if x%2==0 or x<2:
return False
for i in range(2, x):
# x가 해당 수로 나누어떨어진다면
if x % i == 0:
return False # 소수가 아님
return True # 소수임
print(is_prime_number(4)) # 4는 소수가 아님
print(is_prime_number(7)) # 7은 소수임
하지만 위 방법은 숫자가 커지면 오래 걸린다
개선된 방법
# 소수 판별 함수(2이상의 자연수에 대하여)
def is_prime_number(x):
if x==2 or x==3:
return True
if x%2==0 or x<2:
return False
for i in range(2, (x**0.5)+1, 2): # 반만 2칸씩 확인한다
# x가 해당 수로 나누어떨어진다면
if x % i == 0:
return False # 소수가 아님
return True # 소수임
print(is_prime_number(4)) # 4는 소수가 아님
print(is_prime_number(7)) # 7은 소수임
첫번째 코드처럼 문제를 풀면 이렇게 풀린다.
import sys
sys.stdin=open('input.txt','r')
if __name__=="__main__":
N=int(input())
res=[]
if N==2:
print(1)
exit()
for num in range(2,N):
for i in range(2,num):
if num%i==0:
break
else:
res.append(num)
print(len(res))
근데 이 방법은 엄청 느리다.
최종답
'''
ch=[0]*N을 만듬
2일때 2의 배수들은 모두 체크를 함
3일때 3의 배수들을 모두 체크함
5의 배수들을 모두 체크함
'''
import sys
sys.stdin=open('input.txt','r')
if __name__=="__main__":
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): # i부터 끝까지 i배수들을 체크해줌
ch[j]=1
print(cnt)
