입력 코드
#include <stdio.h>
int arr[246913];
int main() {
arr[1] = arr[0] = 1;
int i, j;
for (i = 2; i < 246913; i++) {
if(!arr[i])
for (j = i + i; j < 246913; j += i) {
arr[j] = 1;
}
}
while (1) {
int N, cnt = 0;
scanf("%d", &N);
if (!N)
break;
for (i = N + 1; i <= 2 * N; i++) {
if (!arr[i])
cnt++;
}
printf("%d\n", cnt);
}
}
코드 설명
#수학 #정수론 #소수판정 #에라토스테네스의체
#include <stdio.h>
int primenumber(int n) {
int i, j;
int count = 0;
for(i=n+1;i<=2*n;i++){
for (j = 2; j < i; j++) {
if (i%j == 0)
count++;
}
}
return count;
}
main() {
int n;
while (1) {
scanf("%d", &n);
if (n == 0)
break;
else
printf("%d\n", primenumber(n));
}
}
참고
daily-life-in-20s.tistory.com/84
#02. 에라토스테네스의 체(Sieve of Eratosthenes)
소수 판정법 중 하나 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 2는 소수이므로 오른쪽에 2를 쓴다. 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므
daily-life-in-20s.tistory.com
icanyoucanwecan.tistory.com/29
[BEAKJOON] 4948_베르트랑 공준_C언어
https://www.acmicpc.net/problem/4948 풀이 에라토스테네스의 체를 이용하여 소수들을 모두 구한 후, n+1이상 2n이하의 소수의 개수를 출력하면 되는 문제. 에라토스테네스의 체는 간단히 설명하면 2를 제
icanyoucanwecan.tistory.com
[C언어] 백준알고리즘 4948번 베르트랑 공준 문제 (에라토스테네스의 체)
https://www.acmicpc.net/problem/4948 문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 184
evga7.tistory.com
travelerfootprint.tistory.com/m/50?category=900840
백준 알고리즘 4948번: 베르트랑 공준 C언어
문제 출처: https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.
travelerfootprint.tistory.com
문제 출처
4948번: 베르트랑 공준
베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼
www.acmicpc.net
'C' 카테고리의 다른 글
| #76. [백준_C언어] 2108 : 통계학 \ 정렬 (0) | 2021.02.13 |
|---|---|
| #75. [백준_C언어] 11653 : 소인수분해 \ 수학 (0) | 2021.02.12 |
| #73. [백준_C언어] 12971 : 숫자 놀이 \ 수학 (0) | 2021.02.11 |
| #72. [백준_C언어] 1476 : 날짜 계산 \ 수학 (0) | 2021.02.11 |
| #71. [백준_C언어] 9655 : 돌 게임 \ 다이나믹 프로그래밍 (0) | 2021.02.10 |