컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/1990 1990번: 소수인팰린드롬 151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되 www.acmicpc.net 문제 해결 알고리즘 에라토스테네스의 체를 2부터 천만까지 소수판정 후 거기서 a와 b 사이의 수 중 팰린드롬인 수를 출력해준다. 이 때, 천만 이상부터는 소수인 팰린드롬이 없으므로 천만까지만 진행해준다. 아래의 링크에 에라토스테네스의 체 알고리즘이 설명되어있다. https://kimmessi.tistory.com/152?category=871925 [알고리즘] 소수 판정법 - 에라토스..

에라토스테네스의 체란? 고대 그리스 수학자 에라토스테네스가 만든 소수 판정법. 임의의 자연수 $N$에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법. 우선 에라토스테네스의 체를 쓰지 않고 그냥 소수를 구해보자 bool isPrime = true; int N; for(int i=2;i

https://www.acmicpc.net/problem/16563 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net 문제 해결 알고리즘 에라토스테네스의 체를 활용해 MAX값인 5000000까지의 소수들을 전부 구하고 아니라면 그 수가 가지고 있는 가장 큰 소인수를 그 배열에 입력한다. 그러고 주어진 수에 해당되는 배열의 수와 나눠주고 그 나눠준 수는 출력해준다. 이 때, 테스트 케이스의 수가 1000000가 최대이므로 아래의 코드를 이용해주어야한다. cin.tie(0); cout.tie(0); ios_base::sy..