목록에라토스테네스의 체 (5)

반갑습니다!

[백준] 1644 소수의 연속합

1644번: 소수의 연속합 boj.kr 풀이 소수를 찾아 배열에 모두 저장한 뒤, 투 포인터 알고리즘으로 해결하면 된다. 아래의 코드에서는 에라토스테네스의 체를 사용해 소수를 판별했다. 코드 C++ Python3
알고리즘 문제 풀이 2020. 10. 23. 15:01
[백준] 2153 소수 단어

2153번: 소수 단어 boj.kr 풀이 에라토스테네스의 체를 사용해 1부터 최대값인 20 * 52 까지의 범위에 있는 소수를 모두 구한 뒤, 입력 들어온 문자열을 숫자로 바꿔서 소수 여부를 확인했다. 코드 C++ #include using namespace std; const int MAX = 20 * 52; int main() { bool arr[MAX + 1]; for (int i = 1; i
알고리즘 문제 풀이 2020. 10. 5. 22:00
[백준] 6588 골드바흐의 추측

6588번: 골드바흐의 추측 www.acmicpc.net 풀이 에라토스테네스의 체를 사용해서 소수를 모두 구한 뒤, 3부터 시작해서 수를 탐색하기 시작한다. 가장 작은 홀수 소수인 3부터 홀수만 탐색하므로 처음으로 발견되는 두 수의 차이가 가장 크다는 것을 보장할 수 있다. 코드 #include #include using namespace std; bool chk[1000001]; void precalc() { fill(chk, chk + 1000001, true); chk[1] = false; for (int i = 1; i * i n; if (n == 0) break; bool find = false; // 3부터 시작해서 홀수만 탐색 for (int i = 3; i < n; i += 2) { // ..
알고리즘 문제 풀이 2020. 4. 20. 22:45
[프로그래머스] 소수 만들기

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 에라토스테네스의 체를 이용해서 소수를 미리 계산해두고 DFS를 사용하여 숫자 3개를 골라 해결하였다. 코드 #include #include using namespace std; int ans; bool chk[3001]; void precalc() { fill(chk, chk + 3001, true); chk[0] = false; chk[1] = false; for (int i = 2; i * i
알고리즘 문제 풀이 2020. 4. 17. 01:49
[알고리즘] 에라토스테네스의 체

소수 찾기 문제를 풀고 기왕 포스트하는김에 이론정리를 해놓는게 낫겠다는 생각이 들어서 정리하였다. 소수를 찾는 알고리즘이다. 위의 동영상처럼 1부터 N까지 숫자를 순회하며 순회한 수들의 배수를 제거하는 방법이다. 구체적인 구현 방법은 코드를 살펴보자 n을 입력받아서 1~n까지의 숫자 중에서 소수인 숫자를 출력하는 코드이다. #include #include using namespace std; void precalc(vector& prime, int n){ prime[1] = false; for(int i=2; i*i n; vector prime(n+1, true); precalc(prime, n); for(int i=1; i
CS 2020. 4. 8. 22:21
이전 Prev 1 Next 다음