문제:
어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱 ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱 ㄴㄴ수가 몇 개 있는지 출력한다.
입력:
첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000.000보다 작거나 같은 자연수이다.
출력:
첫째 줄에 [min,max]구간에 제곱ㄴㄴ 수가 몇 개인지 출력한다.
풀이방법:
어떤 수 X가 한 제곱수로 나누어지는지 확인하는 것 보다 제곱수가 나누어 떨어지게 만들 수 있는 수들을 지워나가는 것이 시간복잡도를 줄일 수 있다.(에라토스테네스의 체와 비슷)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
check=[0]*1000001
a,b=map(int,input().split())
for i in range(2,b):
if i*i > b:
break
start=i*i-a%(i*i)
if start == i*i:
start = 0
for j in range(start,b-a+1,i*i):
check[j]=1
ans=0
for i in range(b-a+1):
if check[i]==0:
ans+=1
print(ans)
|
cs |
문제링크:
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]5567. 결혼식 (0) | 2019.10.17 |
|---|---|
| [BOJ]1159. 농구 경기 (1) | 2019.10.16 |
| [BOJ]2960. 에라토스테네스의 체 (0) | 2019.10.14 |
| [BOJ]2851. 슈퍼 마리오 (0) | 2019.10.13 |
| [BOJ]17144. 미세먼지 안녕! (0) | 2019.10.12 |