BOJ 1929 소수 구하기

1 개요[ | ]

BOJ 1929 소수 구하기

에라토스테네스의 체를 구현해 봅니다
알고리즘 분류: 에라토스테네스의 체

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 main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int M, N, i;
    cin >> M >> N;
    for(i=M; i<=N; i++) {
        if(isPrime(i)) {
            cout << i << "\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;
	}
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int M = sc.nextInt();
		int N = sc.nextInt();
		for(int i=M; i<=N; i++) {
			if( is_prime(i) ) System.out.println(i);
		}
	}
}

4 PHP[ | ]

에라토스테네스의 체

<?php
$t = 1000000;
$a = array_fill(0,$t+1,0);
for($i=2; $i<$t; $i++) $a[$i] = $i;
$sqrt_t = sqrt($t);
for($i=2; $i<$sqrt_t; $i++) {
    for($j=$i*2; $j<$t; $j+=$i) $a[$j] = 0;
}
fscanf(STDIN,'%d %d',$M,$N);
ob_start();
for($i=$M; $i<=$N; $i++) {
    if( $a[$i] != 0 ) echo $i . "\n";
}
ob_flush();

5 Python[ | ]

에라토스테네스의 체

t = 1000000
a = [0]*(t+1)
for i in range(2,t):
    a[i]=i
for i in range(2,int(t**.5)):
    a[i*2::i]=[0]*((t-i)//i)
M,N=map(int,input().split())
for i in a[M:N+1]:
    if i!=0: print(i)

is_prime() 사용

def is_prime(x):
    import math
    if x<2: return False
    for i in range(2,int(math.sqrt(x))+1):
        if x%i==0: return False
    return True
M,N=map(int,input().split())
for i in range(M, N+1):
    if(is_prime(i)): print(i)

6 같이 보기[ | ]