에라토스테네스

알고리즘/백준(BOJ)

[백준/C++] 1644번 소수의 연속합

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 소수 판별 알고리즘 + 투포인터 알고리즘의 조합이다. 우선, 에라토스테네스의 체를 이용하여 소수를 걸러준다. N의 범위가 4백만이므로 그냥 이중 for문을 사용하면 TLE다. (소수를 거른다는 것은, 소수끼리만 따로 모아준다는 것을 뜻한다. 그렇게 된다면 자연스레 소수들은 연속되게 된다.) 거른 소수를 따로 저장해준 뒤, 이를 이용해 투포인터 알고리즘을 작동시킬 것이다. 필요한 변수들을 선언 해준 뒤, left와 right 사이의 구간합을 구해준다. 이때 구간합이 n보다 작으면 right가 가리키는 소수를 더해준다...

알고리즘/자료구조

에라토스테네스의 체 및 소수 구하기

에라토스테네스의 체(sieve of Eratosthenes) = >N 이하의 소수(prime number)를 모두 정확히 찾아내는 도구 case1. O(N^2) #include #include using namespace std; const int MAX = 1000; int main(){ vector v; for(int i=2; i

beomseok99
'에라토스테네스' 태그의 글 목록