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

4번째 줄: 4번째 줄:
;함수 eratosthenes()
;함수 eratosthenes()
;함수 primes_sieve()
;함수 primes_sieve()
;클래스 PrimeSieve


==PHP==
==PHP==

2018년 8월 25일 (토) 09:19 판

1 개요

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

2 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]
print_r( $sieve );
# Array
# (
#     [0] => 
#     [1] => 
#     [2] => 1
#     [3] => 1
#     [4] => 
#     [5] => 1
#     [6] => 
#     [7] => 1
#     [8] => 
#     [9] => 
#     [10] => 
# )

3 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
sieve = primes_sieve(10)
print( sieve )
# [False, False, True, True, False, True, False, True, False, False, False]
for i in range(1,11):
    print( i, sieve[i] )
# 1 False
# 2 True
# 3 True
# 4 False
# 5 True
# 6 False
# 7 True
# 8 False
# 9 False
# 10 False

4 같이 보기

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