A positive integer greater than 1 which has no other factors except 1 and the number itself is called a prime number.
2, 3, 5, 7 etc. are prime numbers as they do not have any other factors. But 6 is not prime [it is composite] since, 2 x 3 = 6
.
Source Code
# Python program to display all the prime numbers within an interval
lower = 900
upper = 1000
print["Prime numbers between", lower, "and", upper, "are:"]
for num in range[lower, upper + 1]:
# all prime numbers are greater than 1
if num > 1:
for i in range[2, num]:
if [num % i] == 0:
break
else:
print[num]
Output
Prime numbers between 900 and 1000 are: 907 911 919 929 937 941 947 953 967 971 977 983 991 997
Here, we store the interval as lower for lower interval and upper for upper interval, and find prime numbers in that range. Visit this page to learn how to check whether a number is prime or not.
Example to check whether an integer is a prime number or not using for loop and if...else statement. If the number is not prime, it's explained in output why it is not a prime number.
To understand this example, you should have the knowledge of the following Python programming topics:
- Python if...else Statement
- Python for Loop
- Python break and continue
A positive integer greater than 1 which has no other factors except 1 and the number itself is called a prime number. 2, 3, 5,
7 etc. are prime numbers as they do not have any other factors. But 6 is not prime [it is composite] since, 2 x 3 = 6
.
Example 1: Using a flag variable
# Program to check if a number is prime or not
num = 29
# To take input from the user
#num = int[input["Enter a number: "]]
# define a flag variable
flag = False
# prime numbers are greater than 1
if num > 1:
# check for factors
for i in range[2, num]:
if [num % i] == 0:
# if factor is found, set flag to True
flag = True
# break out of loop
break
# check if flag is True
if flag:
print[num, "is not a prime number"]
else:
print[num, "is a prime number"]
In this program, we have checked if num is prime or not. Numbers less than or equal to 1 are not prime numbers. Hence, we only proceed if the num is greater than 1.
We check if num is exactly divisible by any number from 2
to num - 1
. If we find a factor in that range, the
number is not prime, so we set flag to True
and break out of the loop.
Outside the loop, we check if flag
is True
or False
.
- If it is
True
,num
is not a prime number. - If it is
False
,num
is a prime number.
Note: We can improve our program by decreasing the range of numbers where we look for factors.
In the above program, our search range is from 2 to num - 1
.
We could have used the
range, range[2,num//2]
or range[2,math.floor[math.sqrt[num]+1]]
. The latter range is based on the fact that a composite number must have a factor less than or equal to the square root of that number. Otherwise, the number is prime.
You can change the value of variable num in the above source code to check whether a number is prime or not for other integers.
In Python, we can also use the for...else
statement to do this task without using an additional flag
variable.
Example 2: Using a for...else statement
# Program to check if a number is prime or not
num = 407
# To take input from the user
#num = int[input["Enter a number: "]]
# prime numbers are greater than 1
if num > 1:
# check for factors
for i in range[2,num]:
if [num % i] == 0:
print[num,"is not a prime number"]
print[i,"times",num//i,"is",num]
break
else:
print[num,"is a prime number"]
# if input number is less than
# or equal to 1, it is not prime
else:
print[num,"is not a prime number"]
Output
407 is not a prime number 11 times 37 is 407
Here, we have used a for..else
statement to check if num
is prime.
It works on the logic that the else
clause of the for
loop runs if and only if we don't break out the for
loop. That condition is met only when no factors are found, which means that the given number is prime.
So, in the else
clause, we print that the number is prime.
View Discussion
Improve Article
Save Article
View Discussion
Improve Article
Save Article
Given two positive integers start and end. The task is to write a Python program to print all Prime numbers in an Interval.
Definition: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first few prime numbers are {2, 3, 5, 7, 11, ….}.
The idea to solve this problem is to iterate the val from start to end using a for loop and for every number, if it is greater than 1, check if it divides n. If we find any other number which divides, print that value.
Below is the Python implementation:
Python3
def
prime[x, y]:
prime_list
=
[]
for
i
in
range
[x, y]:
if
i
=
=
0
or
i
=
=
1
:
continue
else
:
for
j
in
range
[
2
,
int
[i
/
2
]
+
1
]:
if
i
%
j
=
=
0
:
break
else
:
prime_list.append[i]
return
prime_list
starting_range
=
2
ending_range
=
7
lst
=
prime[starting_range, ending_range]
if
len
[lst]
=
=
0
:
print
[
"There are no prime numbers in this range"
]
else
:
print
[
"The prime numbers in this range are: "
, lst]
Output:
The prime numbers in this range are: [2,3,5]
Time Complexity: O[N2], where N is the size of the range.
Auxiliary Space: O[N], since N extra space has been taken.
The above solution can be optimized using the Sieve of Eratosthenes. Please see print prime numbers in a range for details.