Write a program that outputs the prime numbers from 1 to N when the natural number N is entered. If 20 is entered, the prime numbers from 1 to 20 are 2, 3, 5, 7, 11, 13, 17, and 19. The time limit is 1 second.
Input:
The first line is given the number of natural numbers N (2<=N<=200,000).
Output:
Prints a prime number on the first line.
Input Example:
20
Output Example:
8
Solution
- I first thought of using multiple for loops, but this question is asking to use Sieve of Eratosthenes
- Sieve of Eratosthenes: getting rid of 1, multiples of 2, multiples of 3, multiples of 5.... to find the prime number (make sure to include 2,3,5... in the list)
- create a blank list(ch) that will include all the numbers in between 0 to n (n+1)
- create cnt to count the prime numbers
- the first for loop will increase the cnt as they are the prime numbers (2,3,5,7... they are not a multiples of numbers)
- in the next for loop, it will insert 1 in ch if they are multiples of i (2,3,5,7..)
ㄴ this is why we set up for loop that includes step (i)
n = int(input())
ch = [0] * (n+1)
cnt = 0
for i in range (2, n+1):
if ch[i] == 0:
cnt += 1 # 2,3,5,7...
for j in range (i, n+1, i):
ch[j] = 1
print(cnt)
@Columbia