본문 바로가기

알고리즘73

[백준/C++] 1929번 : 소수 구하기(시간 초과, 에라토스테네스의 체) 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 풀이 이전 문제를 풀었던 방식대로 했으면 시간 초과가 나는 문제이다. 문제 설명에도 나와있듯, 에라토스테네스의 체를 사용해야 한다. 01. 배열을 만들어 0과 1을 제외한 수를 true로 초기화한다. 02. root(max)까지 돌면서 소수의 n배수, 즉 소수가 아닌 값을 false로 표시한다 03. 배열의 크기만큼 for문을 돌면서 소수인 값을 출력한다. 문제가 잘 풀리지 않을 경우 아래 팁을 참고하면 쉽다. 개인적.. 2021. 8. 7.

[백준/C++] 11653번 : 소인수분해 문제 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. 출력 N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다. 풀이 에라토스테네스의 체를 활용하면 간단히 풀 수 있는 문제이다. 사용하지 않아도 풀 수는 있지만 실행시간이 크게 차이난다. 소수 판별 알고리즘 01) 가장 원초적인 방법 : 2부터 판별하는 수 전까지 나눠보고 나머지가 0이 아니면 소수로 정의하는 방법. 추천하지 않는다 02) 발전된 방법 : 2부터 해당 숫자의 root(N)까지 확인하는 방법이다. 원리는 약수의 중심을 구하는 과정이다 - i N; if (N != 1){ // i*i 2021. 8. 7.

[백준/C++] 2581번 : 소수 문제 자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다. 입력 입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다. M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다. 출력 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. 풀이 지난 소수 문제와 비슷한 문제다! #i.. 2021. 8. 6.

[백준/C++] 1978번 : 소수 찾기 문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력 주어진 수들 중 소수의 개수를 출력한다. 풀이 여기에서 말하는 소수는 Prime Number이다. 01. 1은 소수가 아니다. 02. 2부터 제곱근까지 반복문을 돌리며 배수 여부를 판별한다. #include #include using namespace std; int main(){ int N, num, cnt=0; cin >> N; bool isPrime = true; for (int i = 0; i> num; if (num == 1){ // 1은 소수가 아님 isPrime = fals.. 2021. 8. 5.

이전 1 ··· 9 10 11 12 13 14 15 ··· 19 다음

티스토리툴바