소수4 [백준 2581/c++] 소수 범위 내 소수를 에라토스테네스의 체를 이용하여 배열로 구하고 해당 수를 배열의 값에서 찾아 소수인지 판별, 소수면 벡터에 넣어서 합과 최소를 구하는 문제이다 https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net #include using namespace std; int main() { int m, n, sum, min; int ar[10004]; vector v; cin >> m >> n; for (int i = 2; i 2022. 7. 12. [백준 1978/c++] 소수 찾기 간단하게 소수인지 판별하는 함수만 만들어주면 되는 문제이다 너무 간단하니 오늘은 다른 문제도 풀자 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net #include using namespace std; bool check_prime(int a) { for (int i=2; i> n; for (int i=0; i> m; if (m==1) { continue; } else if (check_prime(m)) { cnt++; } } cout 2022. 7. 12. 소수 판별하기, 범위 내 소수 구하기 저번에 간단하게 올렸었지만 코드로는 이해 못해서 버벅거리니 하나하나 꼼꼼히 다시 정리하려한다 특정한 수의 소수 판별 함수 소수는 자기 자신과 1이외의 수로 나누어 떨어지지 않아야 하므로( 자신과 1 외에 약수가 없어야 하므로) 소수 판별 함수를 간단히 코드로 구현하면 아래와 같다 bool isPrimeNumber(int a){ // 0은 물론이고, 1과 자기자신외의 숫자로 자신이 나눠져 떨어지는지 보므로 범위는 2이상, n 미만이다 for(int i=2; i 2022. 6. 18. 에라토스테네스의 체, 소수판별법 에라토스테네스의 체 소수를 걸러내는 방법, 소수의 배수(합성수)들을 하나씩 지워나가 남는 것들은 소수라는 결론에 도달하는 방식이다 소수 판별법 소수는 1 과 자기 자신으로만 나누어 떨어지므로, n 이하의 모든 자연수를 대입하여 1외에 수로 나누어 떨어지는지 확인하면 되지만 모두 계산할 필요없이 n의 제곱근 이하의 값이 1외의 수로 나누어 떨어지는지 확인하면 된다 왜냐하면 n 이 소수가 아닌 합성수라면, n = a * b 로 나타낼 수 있는데(a,b는 1외의 자연수) a와 b는 모두 n의 제곱근 이하의 값을 가지므로, n의 제곱근에서 나누어지는 수(a와 b) 가 있는지만 확인하면 소수인지 아닌지를 구분 가능한것이다. 제곱근 n이하에서 나누어 떨어지면 합성수, 나누어 떨어지지 않으면 그 수는 소수이다 2022. 6. 10. 이전 1 다음