에라토스테네의 체 검색 결과
1 개의 검색 결과가 있습니다.
ProblemSolving

에라토스테네의 체

에라토스테네스의 체는 소수를 찾는 방법이다. 2부터 시작해서 소수의 배수들을 모두 제거하는 알고리즘을 통해 대량의 소수를 구할 수 있다. #define bigNum 1000000001 bool primeNumber[bigNum]; void setPrime() { for (int i = 2; i < bigNum; i++) { primeNumber[i] = true; } for (int i = 2; i < bigNum; i++) { if (!primeNumber[i]) continue; for (int j = 2 * i; j < bigNum; j += i) { primeNumber[j] = false; } } } 10^9개의 소수를 구하는데 약 18초가 소요된다.

2021. 2. 26. 03:33