카카오 자꾸 소수 판별 나로는데 뭐길래 그러냐

[익명(111.91)]

에라토스테네스의 체가 정석 아니냐?

제곱근까지 구한다는 왜 자꾸 나오는거

[c언어입학(112.153)]

원래 제곱근으로 구하는게 맞는데 뭔 소리임

[익명(111.91)]

그니까 에라토스테네스 쓰면 원래 제곱근까지만 딱 구하는데 넌 뭔소리하냐

[c언어입학(112.153)]

https://www.acmicpc.net/submit/6588/31888513
이거 풀어보셈

[익명(111.91)]

그거 이미 풀었는데

[c언어입학(112.153)]

?? 소수판별할 때 제곱근 이용해서 안 풀었음? 1부터 n까지 i문 돌아가고 1부터 n까지 j문 돌아서 나눠지면 소수가 아니다 이런식으로 돌리면 시간초과 뜨잖아

[익명(111.91)]

아 제곱근이 범위 말하는거임 ? 소수 구할때 ?

[익명(111.91)]

그럼 다른 애들은 그냥 직관적으로 이중포문 돌려서 시간초과 떳다고 그러고 있는 것임??

[c언어입학(112.153)]

글을 안 읽어봐서 모르겠음

[익명(182.225)]

아리스토 텔레스 체의 일부 아니냐 제곱근으로 판별이

[익명(14.33)]

채 하나하나 구하고있으면 타임오버 ㅅㄱ

[익명(111.91)]

문제를 모르니까 먼말인지를 모르겟노

[익명(14.33)]

에라토스테네스 체는 루트n까지 소수 구해도 (루트n)^2이니까 시간복잡도가 n이잖아 그냥 루트n까지 나눠보는건 루트n번이면됨 물론 한번만들어노면 계속 쓸수있으니까 판별해야될게 존나많으면 채가나은데 몇개 판별 안하면 걍 일일이 나눠보는게 나음

[익명(111.91)]

아 대충 먼말인지 알겠다 ㄱㅅㄱㅅ 수 몇개만 소수로 판별하면 되는 문제였나 보구나

[익명(14.33)]

그리고 뭐가 최대인지 바로아는것도 아니라 상한정하는것도 일이라서

[익명(111.91)]

문제를 모르겠는데 쨋든 ㄱㅅㄱㅅ

[익명(175.197)]

다시공부해라

[익명(14.38)]

에라토스테네스의 체 자체가 제곱근까지만 하면 된다는 생각이 이어져서 나온거임

[익명(111.91)]

ㅇㅇ 원래 소수 구할때 제곱근 까지만 돌리면 되잖아

[익명(14.38)]

근데 코드로 체 만들기 귀찮으니까 그냥 제곱근까지 하게 대충 몇줄 치고 끝냈겠지

[익명(221.149)]

모든 소수를 판별할 필요가 없으니까 에라토스테네스의 체의 일부 과정을 사용한 거지.