"에라토스테네스의 체 구현 함수 eratosthenes()"의 두 판 사이의 차이

20번째 줄: 20번째 줄:
     }
     }
     }
     }
    System.out.println(Arrays.toString(not_prime));
    // [1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0]
     for(int i=1; i<=MAX; i++) {
     for(int i=1; i<=MAX; i++) {
     if( not_prime[i] == 0 )
     if( not_prime[i] == 0 )

2018년 12월 24일 (월) 18:29 판

1 개요

에라토스테네스의 체 구현
함수 eratosthenes()
함수 primes_sieve()

2 Java

import java.util.*;
public class Solution {
    public static void main(String[] args) {
    	int MAX = 17;
    	int[] not_prime = new int[MAX+1];
    	not_prime[0] = 1;
    	not_prime[1] = 1;
    	for(int i=2; i<=Math.sqrt(MAX); i++) {
    		for(int j=i*2; j<=MAX; j+=i) {
    			not_prime[j] = 1;
    		}
    	}
    	System.out.println(Arrays.toString(not_prime));
    	// [1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0]
    	for(int i=1; i<=MAX; i++) {
    		if( not_prime[i] == 0 )
    			System.out.format("%d ", i );
    			// 2 3 5 7 11 13 17 
    	}
    }
}
import java.util.*;
public class MyClass {
	static boolean[] primes_sieve(int max) {
		boolean[] a = new boolean[max+1];
		Arrays.fill(a, Boolean.TRUE);
		a[0] = a[1] = false;
		int i, j;
		for(i=2; i<=max; i++) {
			for(j=i*2; j<=max; j+=i) a[j] = false;
		}
		return a;
	}
	public static void main(String[] args) {
		System.out.println( Arrays.toString(primes_sieve(10)) );
		// [false, false, true, true, false, true, false, true, false, false, false]
		System.out.println( Arrays.toString(primes_sieve(11)) );
		// [false, false, true, true, false, true, false, true, false, false, false, true]
	}
}
import java.util.*;
public class MyClass {
	static boolean[] primes_sieve(int max) {
		boolean[] a = new boolean[max+1];
		Arrays.fill(a, Boolean.TRUE);
		a[0] = a[1] = false;
		int i, j;
		for(i=2; i<=Math.sqrt(max); i++) {
			for(j=i*2; j<=max; j+=i) a[j] = false;
		}
		return a;
	}
	public static void main(String[] args) {
		System.out.println( Arrays.toString(primes_sieve(10)) );
		// [false, false, true, true, false, true, false, true, false, false, false]
		System.out.println( Arrays.toString(primes_sieve(11)) );
		// [false, false, true, true, false, true, false, true, false, false, false, true]
	}
}

3 PHP

<?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;
}
$sieve = primes_sieve(10);
echo json_encode( $sieve ) . "\n";
# [false,false,true,true,false,true,false,true,false,false,false]
$sieve = primes_sieve(11);
echo json_encode( $sieve ) . "\n";
# [false,false,true,true,false,true,false,true,false,false,false,true]

4 Python

def primes_sieve(size):
    a = [False]*2 + [True]*(size-1)
    for i in range(2,int(size**.5)+1):
        a[i*2::i]=[False]*((size-i)//i)
    return a
print( primes_sieve(10) )
# [False, False, True, True, False, True, False, True, False, False, False]
print( primes_sieve(11) )
# [False, False, True, True, False, True, False, True, False, False, False, True]

5 같이 보기

문서 댓글 ({{ doc_comments.length }})
{{ comment.name }} {{ comment.created | snstime }}