Finding prime numbers (소수 찾기)

Question

Return the number of prime numbers between 1 and the given number n.

The prime number can be divided only by 1 and itself.

(1 is not a prime number)

 

Limitation

• n a natural number that is more than or equal to 2 and less than or equal to 1000000.

 

Example of I/O

n	result	description
10	4	4 prime numbers [2, 3, 5, 7] between 1 and 10.
5	3	3 prime numbers [2, 3, 5] between 3 and 5.

 

My Solution 1

def solution(n):
    answer = 0

    for x in range(2, n + 1):
        isPrime = True
        for y in range(2, x - 1):
            if(x%y == 0):
                isPrime = False
        if(isPrime):
            answer += 1
            
    return answer

# This solution can be used to find the answer.
# However, it can not pass the quiz because the time takes too long.

 

My Solution 2 with Sieve of Eratosthenes

def solution(n):
    answer = 0

    # a list including all positive integers less than n.
    # excluding even numbers which are multiples of 2
    prime_numbers = set([x for x in range(3, n + 1, 2)])

    for x in range(3, n + 1, 2):
        if x in prime_numbers:
            # eliminate numbers which are multiples of x
            prime_numbers -= set([x for x in range(x * 2, n + 1, x)])
    
    # add 1 because prime_numbers does not include 2
    answer = len(prime_numbers) + 1
            
    return answer

 

Explanation

 

References

프로그래머스 코딩테스트 연습 - 소수찾기