Table of Contents
Introduction
The task is to print all the prime numbers smaller than or equal to the given number n (given n must be small).
Program
def SOE(ip_num): # Initialize all the element with True, the value will be False if p_num[val] is not prime p_num = [True for val in range(ip_num + 1)] i = 2 while (i * i <= ip_num): # Check if num is prime if (p_num[i] == True): # Find multiples of prime number for val in range(i * 2, ip_num + 1, i): p_num[val] = False i += 1 p_num[0]= False p_num[1]= False for i in range(ip_num + 1): if p_num[i]: # Print prime numbers print(i) ip_num = int(input("Enter the number: ")) print("The primes numbers smaller than equal to {0} are: ".format(ip_num ) ) SOE(ip_num)
Output
Explanation
Approach:
- List all the prime numbers from 2 to N.
2 | 3 | 4 |
5 | 6 | 7 |
8 | 9 | 10 |
- Find and mark all the numbers divisible by 2 and numbers greater or equal to its square.
2 | 3 | 4 |
5 | 6 | 7 |
8 | 9 | 10 |
- Move to next unmark number i.e. 3 and repeat the step 2.
2 | 3 | 4 |
5 | 6 | 7 |
8 | 9 | 10 |
- Repeat step 2 for all the unmarked numbers.
- Stop when there are no more numbers to eliminate.
2 | 3 | 4 |
5 | 6 | 7 |
8 | 9 | 10 |
- Print all the unmarked numbers. These unmarked numbers are the prime numbers smaller than the given number.
Prime numbers:
2 | 3 | |
5 | 7 | |
9 |
0 Comments