[백준] 1124번 언더프라임 - Python

백준 실버2 1124번 언더프라임 - Python

https://www.acmicpc.net/problem/1124

1124번: 언더프라임

---

문제

---

코드

맞았습니다가 뜬 코드입니다. - 메모리 116572KB | 시간 228ms | 코드 길이 531B

import sys
import math
input = sys.stdin.readline
a, b = map(int, input().rstrip().split())
isPrime = [False]*(b+1) # 소수인지 판정
D = [0]*(b+1) # i의 소인수 개수
for i in range(2, b+1):
    isPrime[i] = True
    if i > 3:
        for d in range(2, int(math.sqrt(i))+1):
            if i % d == 0: # i는 소수가 아님
                D[i] = D[i//d] + 1
                isPrime[i] = False
                break
    if isPrime[i]:
        D[i] = 1
sum = 0
for i in range(a, b+1):
    sum += isPrime[D[i]]
print(sum)

소수의 개수와 소수판정을 한꺼번에 해야 시간초과 오류가 뜨지 않는 문제였습니다.

 

D[i] 에는 i의 소인수의 개수를 담습니다.

• 길이가 b+1 인 D를 선언합니다. 모두 0이 들어있습니다.

isPrime[i] 에는 i가 소수인지 아닌지를 담습니다.

• 길이가 b+1(1~b) 인 isPrime 리스트를 선언합니다. 초기상태는 False입니다.
• False는 소수가 아닌 수, True는 소수인 수를 의미합니다.
• 먼저, i 인덱스가 True라고 해줍니다. 만약 i가 3보다 크다면 소수가 아닐 경우를 따져줍니다.
  • i 가 d 로 나눠진다면 소수가 아닙니다.
  • D[i//d]+1 = D[i] 로 더해주고, isPrimed[i] 에 False를 다시 넣습니다.

이런 작업을 초기에 반복하여 b 크기만큼의 리스트 두개를 이용해 답을 도출해냅니다.

---

Try 1.

시간초과가 뜬 코드입니다. - 코드 길이 420B

import sys
input = sys.stdin.readline
a, b = map(int, input().rstrip().split())
def prime(num):
    cnt = 0
    i = 2
    while 1:
        if num % i == 0:
            num = num // i
            cnt += 1
        else:
            if num == 1:
                break
            i += 1
    return cnt
ans = 0
for n in range(a, b+1):
    res1 = prime(n)
    res2 = prime(res1)
    if res2 == 1:
        ans += 1
print(ans)

• 에라토스테네스의 체를 이용하지 않은 코드입니다.

---

Try 2.

시간초과가 뜬 코드입니다. - 코드 길이 491B

import sys
input = sys.stdin.readline
a, b = map(int, input().rstrip().split())
sieve = [1]*2 + [0]*(b-1) # (0은 소수, 1은 소수가 아닌수)
for i in range(2, b):
    if sieve[i] == 1:
        continue
    for j in range(2*i, b, i):
        sieve[j] = 1
ans = 0
for n in range(a, b+1):
    cnt = 0
    for i in range(1, n):
        if sieve[i] == 0:
            while n % i == 0:
                n = n // i
                cnt += 1
    if sieve[cnt] == 0:
        ans += 1
print(ans)

• 에라토스테네스의 체를 사용한 코드입니다.
• 해당 알고리즘으로 시간 초과를 어떻게 해결해야할지 생각해봤습니다.

---

Try 3. 

시간초과가 뜬 코드입니다. - 코드 길이 613B

import sys
import math
input = sys.stdin.readline
a, b = map(int, input().rstrip().split())
sieve = [1]*2 + [0]*(b-1) # (0은 소수, 1은 소수가 아닌수)
for i in range(2, b+1):
    if sieve[i] == 1:
        continue
    for j in range(2*i, b+1, i):
        sieve[j] = 1
ans = 0
for n in range(a, b+1):
    cnt = 0
    if sieve[n] == 1:
        for i in range(2, n):
            if sieve[i] == 0:
                while n % i == 0:
                    n /= i
                    cnt += 1
                    if n < 2:
                        break
        if sieve[cnt] == 0:
            ans += 1
print(ans)

• a에서 b까지 수를 거치는데 이미 소수인 수는 제외시켜보았습니다.
• 그런데도 시간초과가 나서 구글링을 통해 에라토스테네스의 체 알고리즘 만으로는 시간초과 문제를 해결하기 힘들다는 것을 알게 되었습니다.

---

Search 🔍

• 코드 참고 : https://blog.encrypted.gg/291

---

후기

처음 풀때만해도 너무 쉽네 하면서 풀었는데 시간이 이렇게 끌릴지 몰랐습니다

이어폰 빼고 각성해서 겨우 풀었네요