BOJ 4948 베르트랑 공준

1 개요[ | ]

BOJ 4948 베르트랑 공준

n이 주어졌을때, n보다 크고 2n보다 작거나 같은 소수를 구하는 문제
알고리즘 분류: 에라토스테네스의 체, 구현

2 C++[ | ]

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int n) {
    if(n<2) return false;
    if(n<4) return true;
    if(n%2==0 || n%3==0) return false;
    for(int i=5; i*i<=n; i+=6 ) {
        if(n%i==0 || n%(i+2)==0) return false;
    }
    return true;
}

int count(int n) {
    int cnt = 0;
    for(int i=n+1; i<=2*n; i++) {
        if( isPrime(i) ) cnt++;
    }
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    while(true) {
        cin >> n;
        if(n==0) break;
        cout << count(n) << "\n";
    }
}

3 Java[ | ]

is_prime() 사용

import java.util.Scanner;
public class Main {
	static boolean is_prime(int n) {
		if( n < 2 ) return false;
		if( n < 4 ) return true;
		if( n%2==0 || n%3==0 ) return false;
		for(int i=5; i*i<=n; i+=6 ) if(n%i==0 || n%(i+2)==0) return false;
		return true;
	}
	static int bertrand_count(int n) {
		int count = 0;
		for(int i=n+1; i<=2*n; i++) {
			if( is_prime(i) ) count++;
		}
		return count;
	}
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n;
		while( true ) {
			n = sc.nextInt();
			if( n == 0 ) return;
			System.out.println( bertrand_count(n) );
		}
	}
}

4 PHP[ | ]

primes_sieve() 사용

<?php
function primes_sieve($size) {
    $a = array_fill(0,$size+1,true);
    $a[0] = $a[1] = false;
    for($i=2; $i<=sqrt($size); $i++) {
        for($j=$i*2; $j<=$size; $j+=$i) $a[$j] = false;
    }
    return $a;
}
function bertrand_count($n) {
    global $sieve;
    $count = 0;
    for($i=$n+1; $i<=2*$n; $i++) {
        if( $sieve[$i] ) $count++;
    }
    return $count;
}
$sieve = primes_sieve(123456*2);
ob_start();
while (true) {
    fscanf(STDIN,'%d',$n);
    if($n == 0) break;
    echo bertrand_count($n) . "\n";
}
ob_flush();

is_prime() 사용, 시간초과

<?php
function is_prime($n) {
    if( $n<2 ) return false;
    for($i=2; $i<=sqrt($n); $i++) if($n%$i == 0) return false;
    return true;
}
function bertrand_count($n) {
    $count = 0;
    for($i=$n+1; $i<=2*$n; $i++) {
        if( is_prime($i) ) $count++;
    }
    return $count;
}
ob_start();
while (true) {
    fscanf(STDIN,'%d',$n);
    if($n == 0) break;
    echo bertrand_count($n) . "\n";
}
ob_flush();

5 같이 보기[ | ]