FOR FREE MATERIALS
Prime Number in given range
Back to ProgrammingDescription
Before you see the program please follow prime number checking and prime numbers from 1 to 100.
A number is called a prime number if the number is only divisible by 1 and itself. The prime numbers have exactly two factors- 1 and the number itself.
For example, if the number are 5. 5 is only divisible by 1 and 5. The number of factors of 5 is 2. So, 5 is a prime number.
If the number is 4, it is divisible by 1, 2, and 4. So, instead of 1 and 4, it has another factor 2. The number of factors of 4 is 3. So, it is not a prime number.
So, the main logic of the program is to take the number as input and the number of factors are counted. If the number of factors is 2 then it is a prime number otherwise it is not a prime number.
The program is written here to find the prime numbers between a given range. For each number it is checked for prime, if it is prime then it will be printed.
Algorithm
INPUT: Lower Range and Upper Range.
OUTPUT: Prime numbers between the given ranges.
PROCESS:
Step 1: [Taking the inputs]
Read m, n [The lower limit and upper limit to find prime numbers]
Step 2: [printing the prime numbers between 1 and 100]
For j=m+1 to n-1 repeat
Set c<-0
[counting the number of factors]
For i=1 to j repeat
If j mod i=0 then
Set c<-c+1
[End of ‘if’]
[End of ‘for’ loop]
If c=2 then
Print j
[End of ‘if’]
Step 2: Stop.
Code
Time Complexity:
for(j=m+1;j<n;j++)-----------------------------------------------O(p)
{
c=0;
//counting the number of factors
for(i=1;i<=j;i++)----------------------------------------O(j)
{
if(j%i==0)
c++;
}
if(c==2)
printf("%d ",j);
}
The time complexity of finding prime numbers here is O(p*j) where ‘p’ is the number of elements to be checked for prime and ‘j’ is each number to be checked. For the simplicity of the program here the loop to check prime is executed from 1 to j.
But for more optimization, we can check from 2 to because a number ‘j’ can have maximum number of factors. So, we can say the most optimized complexity is O().
Space Complexity:
The space complexity of this program is O(1) as it requires a constant number of memory spaces to find the prime numbers between the given range.
