에라토스테네스의 체 구현 클래스 Eratosthenes

1 개요[ | ]

에라토스테네스의 체 구현
클래스 Eratosthenes
클래스 PrimeSieve

변수/메소드	설명
변수
size	체의 크기
sieve	체
메소드
생성자	크기를 지정하여 체 생성
isPrime(x)	체를 활용하여 x가 소수인지 판별

2 PHP[ | ]

<?php
class PrimeSieve {
    public $size, $sieve;
    function __construct($size) {
        $this->size = $size;
        $this->sieve = array_fill(0,$size+1,true);
        $this->sieve[0] = $this->sieve[1] = false;
        $temp = sqrt($size);
        for($i=2; $i<=$temp; $i++) {
            for($j=$i*2; $j<=$size; $j+=$i) $this->sieve[$j] = false;
        }
    }
    function isPrime($x) {
        if( !array_key_exists($x,$this->sieve) ) return null;
        return $this->sieve[$x];
    }
}
$ps = new PrimeSieve(10);
echo $ps->size . "\n";
echo json_encode($ps->sieve) . "\n";
# 10
# [false,false,true,true,false,true,false,true,false,false,false]
var_dump($ps->isPrime(1));
var_dump($ps->isPrime(2));
var_dump($ps->isPrime(3));
var_dump($ps->isPrime(4));
var_dump($ps->isPrime(5));
var_dump($ps->isPrime(6));
# bool(false)
# bool(true)
# bool(true)
# bool(false)
# bool(true)
# bool(false)
var_dump($ps->isPrime(-1));
var_dump($ps->isPrime(0.5));
var_dump($ps->isPrime(11));
# NULL
# NULL
# NULL

3 Python[ | ]

class PrimeSieve(object):
    def __init__(self, size):
        self.size = size
        self.sieve = [False]*2 + [True]*(size-1)
        for i in range(2,int(size**.5)+1):
            self.sieve[i*2::i]=[False]*((size-i)//i)
    def isPrime(self, x):
        try:
            if x<0: return None
            return self.sieve[x]
        except:
            return None;
ps = PrimeSieve(10)
print( ps.size )
print( ps.sieve )
# 10
# [False, False, True, True, False, True, False, True, False, False, False]
print( ps.isPrime(1) )
print( ps.isPrime(2) )
print( ps.isPrime(3) )
print( ps.isPrime(4) )
print( ps.isPrime(5) )
print( ps.isPrime(6) )
# False
# True
# True
# False
# True
# False
print( ps.isPrime(-1) )
print( ps.isPrime(0.5) )
print( ps.isPrime(11) )
# None
# None
# None

4 같이 보기[ | ]