728x90
- 문제
https://www.acmicpc.net/problem/4948
4948번: 베르트랑 공준
베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼
www.acmicpc.net
- 풀이법 ( 알고리즘 )
에라토스테네스의 체를 이용해 가능한 범위( 123456 * 2 + 1)까지 소수를 판별 후 각 테스트 케이스에 대해 소수를 판별한다.
- 풀이 - C++ ( C )
더보기
#include <iostream>
#define MAX 123456
using namespace std;
int n; // n : 테스트 케이스
bool isPrime[2 * MAX + 1];
int main(void)
{
//init ( 에라토스테네스의 체 )
isPrime[1] = true;
for (int i = 2; i < 500; i++)
{
for (int j = i * 2; j < MAX * 2 + 1; j += i) // 그 수의 배수부터 가능한 범위까지 지운다.
isPrime[j] = true;
}
//input & solve
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
while (1)
{
cin >> n;
if (n == 0) break; // 입력의 마지막에 0이 주어짐
int cnt = 0;
for (int i = n + 1; i <= n * 2; i++)
if (!isPrime[i]) cnt++;
cout << cnt << "\n";
}
return 0;
}
- 풀이 - JAVA
더보기
import java.util.Scanner;
public class Main {
static boolean[] prime = new boolean[246912 + 1];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
prime[1] = true;
for(int i = 2; i < 500; i++)
{
for(int j = i * 2; j < 246912 + 1; j+=i)
prime[j] = true;
}
while(true) {
int n = sc.nextInt();
int cnt = 0;
// 0인 경우 프로그램 종료
if(n == 0) break;
for(int i = n + 1; i <= 2 * n; i++)
{
if(!prime[i]) cnt++;
}
System.out.println(cnt);
}
}
}
- 풀이 - PYTHON
더보기
import math
def isPrime(x, y):
cnt=0
check = [True] * (y+1)
for i in range(2,int(math.sqrt(y)+1)):
if check[i] == True:
for j in range(i*2, y+1, i):
check[j] = False
for i in range(x+1,y+1):
if check[i] == True:
cnt += 1
return cnt
Prime_list = []
while True:
n = int(input())
if n == 0:
break;
Prime_list.append(isPrime(n,2*n))
for i in Prime_list:
print(i)
728x90
'PS > 백준' 카테고리의 다른 글
[ 백준 ] 14501번 : 퇴사 (0) | 2022.02.26 |
---|---|
[ 백준 ] 14888번 : 연산자 끼워넣기 - ( C++/C , PYTHON/파이썬, JAVA/자바 ) (0) | 2022.02.25 |
[ 백준 ] 1931번 : 회의실 배정 - ( C++/C , JAVA/자바, PYTHON/파이썬 ) (0) | 2022.02.25 |
[ 백준 ] 2581번 : 소수 - ( C++/C , JAVA/자바, PYTHON/파이썬 ) (0) | 2022.02.25 |
[ 백준 ] 7568번 : 덩치 - (C++/C , JAVA/자바 , PYTHON / 파이썬) (0) | 2022.02.25 |