100만 이하의 소수들을 모두 출력하는 문제.
소수의 조건을 루프를 돌려 일일히 확인하며 구하면 시간초과 발생!
소수의 개념을 생각해보면, 임의의 수에 임의의 수 이전까지의 수 중 하나를 곱한 것은 소수가 아니게 된다.
이를 에라토스 테네스의 체 알고리즘을 구현하여 빠른 시간 내 구할 수 있다.
Solved
for (int i = 2; i < 1000000; i++)
{
for (int j = 2; i*j < 1000000; j++)
{
forCheck[i*j] = 0;
}
}
UnSolved
Tips
루프를 돌리면서 if(i%j==0 && i!=j) 이면 출력! 같은 방식으로 접근하면 시간초과가 발생한다.
branch : minq commit : 41405bd0a8cdacf5a5b2ae41a9a4b211db50185f
About The Problem
Solved
UnSolved
Tips