반례입니다.

체의 값을 500만으로 수정해도 틀렸습니다가 나옵니다...

넣었을때 출력값으 그대로 잘 나오는거같은데...

현재 500만 이상의 소수가 들어오면 틀리게 되어 있습니다.

소수리스트 구하는 범위를 천만으로 수정하고

만약 입력된 n이 소수라면 바로 출력되고 아니면 소인수분해하게 했는데

이젠 시간초과네요... 에라토스 구현했는데 1000만이 너무 많은게 문제일까요..?

1. 에라토스테네스는 1000만까지의 소수의 배수를 다 지우지 않습니다.

2. 소인수분해를 할 때도 모든 소수로 나눠볼 필요가 없습니다.

1. 우선 이 문제의 경우 사실 에라토스테네스의 체를 안쓰셔도 됩니다. (1부터 n/2 까지 1씩 증가시키면서 나누어 떨어질때마다 출력 하는 식으로)

2. 에라토스테네스의 체를 쓰신다면 sqrt(n) 까지만 확인해보셔도 됩니다. 이에 대한 증명도 알고싶으시면 제 블로그 글 중에 써둔게 있습니다.

ㄴwider93

1. 제가 에라토스테네스의 체를 구현때 코딩에 에러가 있어서 다 지우지 못하는건가요? 아니면 원래 에라토스테네스가 한계가 있는건가요?

2. 번내용은 수학적으로 이해가 안됩니다... 아래분 블로그를 한번 보겠습니당

ㄴnahwasa

1.  1씩 증가시키면서 만약 n이 999만대의 소수라면 약 499만번 나누게 되는건가요?

2. 그.. 블로그를 봐도 이해가 잘 안됩니다... 만약 n이 17이라면 4.? 가 제곱근일테고 그럼 에라토스로 걸러낸 소수로 나눌때 4.?보다 작은 2,3 만 가지고도 n이 소수인지 알 수 있는건가요??

수학에 있어서 한눈에 들어오지 않아서 초등학생 가르쳐주듯이 천천히 설명 한번만 해주시면 정말 감사하겠씁니다 ㅠㅠㅠㅠ

n = a*b라고 합시다. 

그러면 a, b  둘 중 하나는 n의 제곱근 이하입니다. 그렇지 않다면 ab > n이 되어 모순입니다. 

따라서 n이 합성수라면 1보다 크고 n**0.5보다 작은 약수가 있습니다. 따라서 n까지 다 나눠볼 필요가 없습니다.

그래서 에라토스테네스의 체는 최대 크기의 제곱근보다 작은 소수에 대해서만 배수를 지우고 나면, 남은 수들은 모두 소수입니다.

소인수분해도 비슷합니다.

ㄴnahwasa

1. 1씩 증가시키면서 만약 n이 999만대의 소수라면 약 499만번 나누게 되는건가요?

-> 넹. 사실 아래와 같은 코드만으로도 통과 가능합니다. (제가 파이썬은 잘 몰라서 좀 비효율적인 코드 있더라도 이해해주세요)

import sys
input = sys.stdin.readline

n = int(input())
for i in range(2, n+1):
    while n%i == 0:
        print(i)
        n//=i
    if n==1:
        break

결국 에라토스테네스의 체가 효율적인 부분은 만약 N이 여러번 들어온다고 생각하면, 미리 최대 수치의 N까지 에라토스테네스의 체로 계산해두고 연산하면 이득이긴 합니다. 하지만 이 문제와 같은 경우 어차피 N이 한 번 들어오므로 에라토스테네스의 체가 그리 효율적으로 보이진 않습니다. 그래도 후보군을 미리 소수를 구해서 좀 더 적은 범위로 만들고, 그걸로 나눠보는 아이디어 자체는 매우 좋은 것 같아요.

2. 그.. 블로그를 봐도 이해가 잘 안됩니다... 만약 n이 17이라면 4.? 가 제곱근일테고 그럼 에라토스로 걸러낸 소수로 나눌때 4.?보다 작은 2,3 만 가지고도 n이 소수인지 알 수 있는건가요?? 수학에 있어서 한눈에 들어오지 않아서 초등학생 가르쳐주듯이 천천히 설명 한번만 해주시면 정말 감사하겠씁니다 ㅠㅠㅠㅠ

-> 윗분이 추가로 설명해주셨네요! 네네 17이라면 4.x 정도일테니 4까지만 보면 됩니다.

그러니까 어떠한 수 n은 자연수 a, b에 대해 a * b라고 표현할 수 있어요. 그리고 또 m = sqrt(n) 이라 한다면 m * m도 n이라고 할 수 있죠.

따라서 a * b == m * m 이라고 할 수 있어요. 그럼 이 상태에서 나올 수 있는 경우는 다음의 세가지 입니다.

A. a=m, b=m (그럼 m도 자연수 였어야 겠죠.)

B. a>m, b<m

C. a<m, b>m

그럼 위 세가지 경우를 다 살펴보면 결국 min(a,b) <= m 인것을 알 수 있어요.

즉, n의 약수인 a와 b가 어떠한 것일지라도 둘 중 하나는 무조건 m(=sqrt(n))보다 작거나 같아요. 그러니 sqrt(n) 까지만 조사한다면 n이 소수인지 아닌지는 알 수 있게 되는거에요.

그럼 이건 n 단 하나에 대한 것이 아니냐고 하실 수 있는데, 결국 n 미만의 모든 자연수들은 n보다 작잖아요? 예를들어 n보다 작은 것 중 가장 큰 수인 n-1 조차도 어쨌든 sqrt(n) > sqrt(n-1) 이거든요. 그러니 n 이하의 모든 자연수에 대해 sqrt(n)까지만 보면 소수 판별이 가능한거죠.

ㄴwider93

ㄴnahwasa

두분 모두 감사합니다!

말씀해주셧던 내용들 기반으로 최대n인 천만 기준 소수를 구해보고 일일히 비교해보면서 증명 내용들을 이해했습니다! 친절히 설명해주셔서 너무 감사합니다!!

나중에 코드 최적화도 도전해봐야겠네요

다시한번 감사드립니다~!