💡백준 4948
◽ 문제
◽ 입력 & 출력
◽ 풀이
✅처음 풀이
- 2번이나 시간초과가 났다.
- 범위를 줄여도 마찬가지로 매번 입력때마다 반복문에들어가 소수를 구해서인거같다..
✅ 성공 풀이
- 2,3번째 줄: num의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사하면 되기 때문에 sqrt를 import해주고, readline()을 위한 sys를 import해준다.
-
check_prime(): 에라토스테네스의 체를 소수면 True
소수가 아니면False로 저장하는 함수로 구현했다.- 먼저 1은 소수가 아니기 때문에 1을 제외시켜주고, 2~ sqrt(num)+1만큼 범위를 지정해준다.
- 20까지 안구하고 4까지만 계산하면되기때문에 범위를 줄여주는 코드이다.
-
li에다가 2~ 123456 * 2 범위 만큼의 숫자를 넣어주고
-
소수를 저장할 prime_list 리스트를 선언
-
함수에 i값을 넣어 값이 소수인지 아닌지 판단한다.
-
만약 소수면 check_prime()의 반환값이 True이기 때문에 if 문은 참이되고, prime_list에 append()해준다.
- 소수가 잘 들어갔는지 확인해보기위해 출력해 확인 보면 예제 입력에서
1 ➡️ n보다 크고, 2n보다 작거나 같은 소수의 개수 = 1개
10 ➡️ n보다 크고, 2n보다 작거나 같은 소수의 개수 = 4개
13 ➡️ n보다 크고, 2n보다 작거나 같은 소수의 개수 = 3개
100 ➡️ n보다 크고, 2n보다 작거나 같은 소수의 개수 = 21개
-
마지막으로 while문을 이용해 계속 입력받는다.
-
n < 소수의 개수 <= 2n의 개수를 구하기 위해 prime_count변수를 초기화한다.
-
만약 입력받은 값이 0이면 while문을 종료한다.
- 소수 값이 잘 나오는 지 보기 위해 확인 해보면 잘 나오는 것을 볼 수 있다.
-
그 다음 범위 내의 소수를 if문에서 검사해 참이면 소수의 개수prime_count를 +1해주고 출력한다.
