Python Prime Generator program Codechef solution
Python Prime Generator program Codechef solution
Problem
Ram wants to generate some prime numbers for his cryptosystem. Help him, please! Your task is to generate all prime numbers between two given numbers.
Warning: large input and output data; be careful with certain languages (though most should be OK if the algorithm is well designed).
Input Format
The first line contains t, the number of test cases (less than or equal to 10).
Followed by t lines, which contain two numbers m and n (1 <= m <= n <= 1000000000, n-m = 100000) separated by a space.
Output Format
For every test case, print all prime numbers p such that m <= p <= n, one number per line. Separate the answers for each test case with an empty line.
Constraints
(1 <= m <= n <= 1000000000, n-m = 100000)
Sample Input:
2
1 10
3 5
Sample Output:
2
3
5
7
3
5
Solution:
|
import math def prime(num):
if num==1 : return 0 if num==2: return 1 if num%2==0: return 0 for i in range(3,int(math.sqrt(num))+1,2): if num%i==0: return 0 return 1 t=int(input(“Enter the number of terms: “)) for a in range(t):
m,num=map(int,input(“Enter 2 numbers: “).split()) count=0 for i in range(m,num+1): if prime(i): print(i) |
Steps to solve this problem:
- Import math module
- Ask the user to enter the number of terms.
- In the loop, ask the user to enter 2 numbers, and using the map() function, get iterator objects and store them in m and num, respectively.
- Initialise the count variable with 0.
- In the loop, pass m as the beginning and n+1 as the end in the range() function.
- Call the prime() function and pass i as an argument. Check if it is true, then print the value of i.
- Define a function prime(num).
- Check if num is equal to 1, then return 0.
- Again, check if num is equal to 2, then return 1.
- Check if num%2 is equal to 0, then return 0.
- In a loop, pass 3 as the beginning, int(math.sqrt(num))+1 as the end, and 2 as the step in the range() function.
- Check if num%i is equal to 0, then return 0.
