FOR FREE CONTENT
Prime Numbers in a given range
Back to ProgrammingDescription
A number is called prime number if the number is only divisible by 1 and itself. The prime numbers has exactly two factors- 1 and the number itself.
For example, if the number is 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 factor 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 ranges. 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.
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.
).
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.
