Programming
Aptitude
Syllabus
Interview Preparation
Interview Exp.
Off Campus
Python program to find Prime Numbers between 1 to100.
Find Prime number between 1 to100
Here, in this page we will discuss program to find Prime number between 1 to100 in python .A prime number is an positive integer that has no divisors except one and itself or can only be exactly divided by the integers 1 and itself without leaving a remainder.
For example n is prime, if n can only be divided by 1 and n. So prime number has two factor one is 1 another is number itself .
The number 1 is neither prime nor composite.
Example:
- n=7
- divisors of 7 are 1 and 7 itself so it is a prime number.
Implementation:
- From 1 to 100 we will start from 2 to check the number of divisors of every number.
- If a number have only two divisors then it is a Prime number.
#To find the prime numbers between 1 to 100
li=[] #list of prime numbers will be stored here
for i in range(2,101):
f=0
for j in range(2,i+1):
if(i!=j and i%j==0): #if any n
f=1
break
if(f==0):
li.append(i)
print('Prime numbers between 1 to 100:')
print(*li,sep=' ')
Output:
Prime numbers between 1 to 100:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Optimal Solution to find prime number between 1 to 100 :
- This method is known as Sieve of Eratosthenes.
- Time Complexity: O(n*log(logn)) .
- Here n is maximum range.
Python Code:
#To find the prime numbers between 1 to 100
li=[True]*(101) #list of prime numbers
li[1]=False
li[0]=False
p=2
while(p*p<=101):
if(li[p]==True): #if it is a prime number then its multiples will be non-prime
for i in range(p*p,101,p):
li[i]=False
p=p+1
print('Prime numbers between 1 to 100:')
for i in range(2,101):
if(li[i]==True):
print(i, end=' ')
Output:
Prime numbers between 1 to 100:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Login/Signup to comment