백준 - 4948번

n=1
while n != 0:
    n = int(input())
    if n == 0:
        break
    sosu = []
    i = n
    t = 2 * n

    for i in range(n, 2 * n):
        check = 0
        if i > 0:
            for k in range(2, i):
                if i % k == 0:
                    check = check + 1
                    break
            if check == 0:
                sosu.append(i)

    print(len(sosu))

이전 소수 계산과 비슷하게 하려 했으나 시간 초과가 떠버렸다. 답은 나올 것이다. 다만 6자리 숫자에서의 효율이 너무 떨어져서 그런 듯하다.

그러나 나에겐 계획이 있지 짝수를 전부 날려버리고 위 과정을 반복하겠다.

 

n=1
while n !=0:
    if n ==0:
        break
    n = int(input())

    sosu = []
    sosu2 = []
    i = n
    t = 2 * n
    for i in range(n+1, t + 1):
        if i % 2 != 0:
            sosu.append(i)
        elif i == 2:
            sosu.append(i)

    z = 0
    x = 2
    for x in sosu:
        check = 0
        if x > 0:
            for k in range(2, x):
                if x % k == 0:
                    check = check + 1
                    break
            if check == 0:
                sosu2.append(x)

    print(len(sosu2))

그렇지만 이 녀석도 실패했다.. 더 효율적인 방법을 찾아보겠다.

 

def sosu(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1): #2배보다 작아질 수가 없기때문에 1,7배 이런건 존재하지 않는다.
        if n % i == 0:
            return False
    return True

answer = list(range(2,246912))

r = []

for i in answer:
    if sosu(i):
        r.append(i)

n = 1
while 1:
    n = int(input())
    count =0
    if n==0:
        break
    for i in r:
        if n<i<=2*n:
            count = count+1
    print(count)

결국 소수를 찾는 함수를 만들어서 구현하고 문제에서 주어준 범위를 미리 입력해서 답지를 만들어 놨다.

이 얼마나 비효율적인 문제인가..

sosu() 부분을 보면 int(n^0.5+1) 이란 것을 볼 수 있는데 생각해보자.

어떤 자연수 n과 m이 있다고 가정하자 m은 n의 2배, 3배, 4배는 될 수 있지만 소수 판별에서 0.7배 1.3배 이런 소수 배들은 의미가 없다.

따라서 m이 100이면 1~50까지만 나눠보면 해당 수가 소수인지 아닌지 알 수 있다는 것이다.

신박한 아이디어다. 좋다!