Problem : Double And Add One
If you like numbers, you may have been fascinated by prime numbers.
Here's a problem related to prime numbers: Accept input numbers N and i. Identify all prime numbers P up to N with the following property:
P1=2*P+1 is also prime
P2=2*P1+1 is also prime
...
Pi=2*P(i-1)+1 is also prime
Example: Inputs N=100, i=3
Let's start with p=2(it is also prime ). Since i=3 we need 3 consecutive prime numbers that satisfy the Double and Add 1 property explained below:
p1=2*p+1 translates to p1=2*2+1=5, which is prime
p2=2*p1+1 translates to p2=2*5+1=11, which is prime
p3=2*p2+1 translates to p3=2*11+1=23, which is prime
Hence p=2 is to be included in the output.
Next, if p=3, the derived numbers are 7, 15, 31 of which 15 is not prime. Hence p=3 is not a solution
Exploring other primes up to 100 in this fashion, we identify the following additional numbers to be included in the solution for i=3:
5 (since the derived numbers 11, 23, 47 are all prime)
89 (since the derived numbers 179, 359, 719 are all prime)
Hence the output would be: 2, 5, 89
Input format for the example: 100 3
Output format for the example: 2 5 89
(Numbers separated by single space)
Here's a problem related to prime numbers: Accept input numbers N and i. Identify all prime numbers P up to N with the following property:
P1=2*P+1 is also prime
P2=2*P1+1 is also prime
...
Pi=2*P(i-1)+1 is also prime
Example: Inputs N=100, i=3
Let's start with p=2(it is also prime ). Since i=3 we need 3 consecutive prime numbers that satisfy the Double and Add 1 property explained below:
p1=2*p+1 translates to p1=2*2+1=5, which is prime
p2=2*p1+1 translates to p2=2*5+1=11, which is prime
p3=2*p2+1 translates to p3=2*11+1=23, which is prime
Hence p=2 is to be included in the output.
Next, if p=3, the derived numbers are 7, 15, 31 of which 15 is not prime. Hence p=3 is not a solution
Exploring other primes up to 100 in this fashion, we identify the following additional numbers to be included in the solution for i=3:
5 (since the derived numbers 11, 23, 47 are all prime)
89 (since the derived numbers 179, 359, 719 are all prime)
Hence the output would be: 2, 5, 89
Input format for the example: 100 3
Output format for the example: 2 5 89
(Numbers separated by single space)
Input Format:
First line contains an integer N
Second line contains integer i
First line contains an integer N
Second line contains integer i
Output Format:
Space delimited prime numbers satisfying Double and Add 1 property in the given range N
Space delimited prime numbers satisfying Double and Add 1 property in the given range N
Constraints:
- 2< N <= 100000
- 1< i <= 10
| EXAMPLE NUMBER | SAMPLE INPUT | SAMPLE OUTPUT |
|---|---|---|
| 1 | 100 3 | 2 5 89 |
| 2 | 20 2 | 2 5 11 |
Solution Source code :-
#include<iostream>
using namespace std;
bool primcheck ( int a)
{
int temp=0;
for(int i=2;i<a;i++)
{
if(a%i==0)
temp++;
}
if(temp==0)
return true;
else
return false;
}
int main()
{
int N,in,temp=0,a;
cout<<"Enter N and i =";
cin>>N>>in;
for(int i=2;i<N;i++)
{
if(primcheck(i))
{
a=i;
for(int j=0;j<in;j++)
{
a=a*2+1;
if(!(primcheck(a)))
temp++;
}
if(temp==0)
cout<<i<<endl;
}
temp=0;
}
}
No comments:
Post a Comment