230110 TIL

problem description
Create a function, solution, that returns the number of prime numbers between 1 and the number n entered.

A prime number is a number divisible only by 1 and itself.
(1 is not prime.)

constraints
n is a natural number greater than or equal to 2 and less than or equal to 1000000.

I/O example

n result
10 4
5 3

I/O Example Description
I/O example #1
Returns 4 because there are 4 primes between 1 and 10 [2,3,5,7]

I/O Example #2
Returns 3 because there are 3 primes between 1 and 5 [2,3,5]

Try my code == Timeout Error

def is_sosu(n):
    for i in range(2, n):
        if n % i != 0:
            pass
        else:
            return 0
    return 1

def solution(n):
    result = 0
    for i in range(2, n + 1):
        answer = is_sosu(i)
        if answer == 1:
            result += 1
    return result
print(solution(1000000))

I tried use my code, but after 10000, I got timeout error. so I tried use the other way which call the Sieve of Eratosthenes.

The time complexity of the Sieve of Eratosthenes algorithm is O(logN), which is fast enough to operate in virtually linear time. Therefore, it is often used in problems where you need to find a prime number of a majority.

However, it has the disadvantage of requiring a lot of memory because it is necessary to allocate a list as large as N when performing the algorithm. Also, it is difficult to use the Sieve of Eratosthenes for the problem of finding whether one billion is prime.

import math


def solution(n):


    array = [True for i in range(n + 1)]
    answer = 0

    for i in range(2, int(math.sqrt(n)) + 1):
        if array[i]:
            j = 2
            while i * j <= n:
                array[i * j] = False
                j += 1

    for i in range(2, n + 1):
        if array[i]:
            answer += 1
    return answer

this code is working well.