발효홍삼
코딩하는 홍삼
발효홍삼
전체 방문자
오늘
어제
  • 분류 전체보기 (142)
    • PS (63)
      • 프로그래머스 (9)
      • 코드업 (10)
      • 백준 (43)
      • 알고스팟 (1)
    • Programming Language (11)
      • html_css (2)
      • java (0)
      • c,c++ (2)
      • vanillajs (2)
      • react (0)
      • vue.js (0)
      • angular.js (0)
      • electron (3)
      • 엄랭(Umjunsik-lang) (1)
      • F# (1)
      • Node.js (0)
      • Go (0)
    • knowledge (41)
      • algorithm (3)
      • data structure (1)
      • os (1)
      • ML (1)
      • math (31)
      • paper review (0)
      • IT-license (4)
    • Programming Guide (27)
      • React (1)
      • Electron (2)
      • CSS , SASS ( SCSS ) , Tailw.. (3)
      • Node.js (1)
      • Go (1)
      • Ruby on Rails (2)
      • R (1)
      • PHP (1)
      • Docker (1)
      • JSP (1)
      • C# (1)
      • Django (1)
      • Flask (1)
      • Dart (1)
      • Next.js (1)
      • Vue.js (1)
      • Unity (1)
      • React Native (0)
      • Flutter (3)
      • GraphQL (1)
      • MongoDB (1)
      • .NET (1)
      • RUST (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • js
  • 프로그래머스
  • 구현
  • java
  • cpp
  • 미분
  • 코드업
  • 기초100제
  • 수학
  • LV1
  • Python
  • 자바
  • electron
  • 적분
  • codeup
  • C
  • HTML
  • 출력
  • 정보처리기능사 필기
  • c++
  • CSS
  • 정보처리기능사
  • 백준
  • 알고리즘
  • 파이썬
  • 미적분학
  • 이산수학
  • nodejs
  • JavaScript
  • 기초백제

최근 댓글

최근 글

티스토리

250x250
hELLO · Designed By 정상우.
발효홍삼

코딩하는 홍삼

[ 백준 ] 4948번 : 베르트랑 공준 - ( C++/C , JAVA/자바, PYTHON/파이썬 )
PS/백준

[ 백준 ] 4948번 : 베르트랑 공준 - ( C++/C , JAVA/자바, PYTHON/파이썬 )

2022. 2. 25. 20:45
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
    'PS/백준' 카테고리의 다른 글
    • [ 백준 ] 14501번 : 퇴사
    • [ 백준 ] 14888번 : 연산자 끼워넣기 - ( C++/C , PYTHON/파이썬, JAVA/자바 )
    • [ 백준 ] 1931번 : 회의실 배정 - ( C++/C , JAVA/자바, PYTHON/파이썬 )
    • [ 백준 ] 2581번 : 소수 - ( C++/C , JAVA/자바, PYTHON/파이썬 )
    발효홍삼
    발효홍삼
    코딩하는 홍삼

    티스토리툴바