prime numbers

[pilhoon]

https://primes.utm.edu/howmany.html

재미로 나도 해봤는데 10억 이하의 소수 개수(50847534) 구하는데 8시간정도 걸렸다 ㅋㅋ 답이라도 맞아서 다행이다 ㅋㅋ

[pilhoon]

계산해둔게 아까우니.. ㅋ 5천만번째 소수(1번째 소수는 2)는 982451653 검색하면 그냥 나오기는 하네 https://primes.utm.edu/curios/page.php/982451653.html

[pilhoon]

이게 알고리즘이 거지같아서 오래걸렸구먼 ㅋ 인터넷에 떠다니는걸로 하니까 5분7초만에 나옴

def SieveOfEratosthenes(n): 

    # Create a boolean array "prime[0..n]" and initialize 
    # all entries it as true. A value in prime[i] will 
    # finally be false if i is Not a prime, else true. 
    prime = [True for i in range(n + 1)] 
    p = 2
    while (p * p <= n): 

        # If prime[p] is not changed, then it is a prime 
        if prime[p]: 
            # Update all multiples of p 
            for i in range(p * 2, n + 1, p): 
                prime[i] = False
        p += 1
    prime[0]= False
    prime[1]= False
    # Print all prime numbers 
    return prime

n = 1_000_000_000
print("Following are the prime numbers smaller")
#Use print("Following are the prime numbers smaller") for Python 3 
print("than or equal to", n )
#Use print("than or equal to", n) for Python 3 
sum(SieveOfEratosthenes(n))

[pilhoon]

np쓰면 훨씬 빠르다고 함 ㅋㅋㅋㅋ

[pilhoon]

https://github.com/kimwalisch/primesieve-python 엄청나구만