Given two numbers n1 and n2. Find prime numbers between n1 and n2, then make all possible unique combinations of numbers from the prime numbers list you found in step 1.
From this new list, again find all prime numbers. Find smallest (a) and largest (b) number from the 2nd generated list, also count of this list.
Consider smallest and largest number as the 1st and 2nd number to generate Fibonacci series respectively till the count (number of primes in the 2nd list).
Print the last number of a Fibonacci series as an output
Constraints
2 <= n1, n2 <= 100 n2 – n1 >= 35
Input
One line containing two space separated integers n1 and n2.
Output
Last number of a generated Fibonacci series.
Sample Input and Output
Example 1
Input
2 40
Output
13158006689
Explanation
1st prime list = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
Combination of all the primes = [23, 25, 27, 211, 213, 217, 219, 223, 229,231, 32, 35, 37, 311, 313, 319, 323, 329, 331, 337, 52, 53, 57, 511, 513, 517,519, 523, 529, 531, 537, 72, 73, 75, 711, 713, 717, 719, 723, 729, 731, 737,112, 113, 115, 117, 1113, 1117, 1119, 1123, 1129, 1131, 1137, 132, 133,135, 137, 1311, 1317, 1319, 1323, 1329, 1331, 1337, 172, 173, 175, 177,1711, 1713, 1719, 1723, 1729, 1731, 1737, 192, 193, 195, 197, 1911, 1913,1917, 1923, 1929, 1931, 1937, 232, 233, 235, 237, 2311, 2313, 2317, 2319,2329, 2331, 2337, 292, 293, 295, 297, 2911, 2913, 2917, 2919, 2923, 2931,2937, 312, 315, 317, 3111, 3113, 3117, 3119, 3123, 3129, 3137, 372, 373,375, 377, 3711, 3713, 3717, 3719, 3723, 3729, 3731]
2nd prime list=[193, 3137, 197, 2311, 3719, 73, 137, 331, 523, 1931, 719,337, 211, 23, 1117, 223, 1123, 229, 37, 293, 2917, 1319, 1129, 233, 173,3119, 113, 53, 373, 311, 313, 1913, 1723, 317]
smallest (a) = 23
largest (b) = 3719
Therefore, the last number of a Fibonacci series i.e. 34th Fibonacci number in the series that has 23 and 3719 as the first 2 numbers is 13158006689
Example 2
Input
30 70
Output
2027041
Explanation
1st prime list=[31, 37, 41, 43, 47, 53, 59, 61, 67]
2nd prime list generated form combination of 1st prime list = [3137, 5953, 5347, 6761, 3761, 4337, 6737, 6131, 3767, 4759, 4153, 3167, 4159, 6143]
smallest prime in 2nd list=3137
largest prime in 2nd list=6761
Therefore, the last number of a Fibonacci series i.e. 14th Fibonacci number in the series that has 3137 and 6761 as the first 2 numbers is 2027041
CODE
Suggest us your solution by commenting it down.
/*
ip: [n1,n2] -> primes range
1) list 1: [primes between n1 & n2]
2) list 2: [primes in: (combinations of all primes from list 1)]
3) smallest,largest in list 2 and N=length of list 2
4) print Nth element in fib series with fib[0]=smallest,fib[1]=largest
*/
#include
using namespace std;
//to check primality
bool isPrime(int n){
if(n==2) return true;
if(n<=1 || n%2==0) return false;
for(int i=3;i<=sqrt(n);i=i+1)
if(n%i==0) return false;
return true;
}
//combines numbers
int conNumbers(int n, int m){
string s="";
while(m!=0){
s+= to_string(m%10);
cout<<"s="<<s<<endl;
m/=10;
}
double x = pow(10, s.length());
n *= x;
//concatenate m to n
for(int i=0; i<s.length(); i++)
n+= (s[i]-'0') * pow(10, i);
return n;
}
//return nth element in fibonacci series
long long int nthFib(int smallest,int largest,int length){
long long int fib[length];
fib[0]=smallest;
fib[1]=largest;
for(int i=2;i<length;i++){
fib[i]=fib[i-1]+fib[i-2];
}
return fib[length-1];
}
//returns answer
long long int solution(int n1,int n2){
vector list1;//to store list 1, ie primes between n1 and n2
//generates prime list
for(int i=n1;i<=n2;i++)
if(isPrime(i))
list1.push_back(i);
set primeCombi; //to store combinations which are prime
for(int i=0; i<list1.size(); i++)
for(int j=0; j>n1>>n2;
cout<<solution(n1,n2);
return 0;
}
/*
ip: [n1,n2] -> primes range
1) list 1: [primes between n1 & n2]
2) list 2: [primes in: (combinations of all primes from list 1)]
3) smallest,largest in list 2 and N=length of list 2
4) print Nth element in fib series with fib[0]=smallest,fib[1]=largest
*/
#include<bits/stdc++.h>
using namespace std;
//to check primality
bool isPrime(int n){
if(n==2) return true;
if(n<=1 || n%2==0) return false;
for(int i=3;i<=sqrt(n);i=i+1)
if(n%i==0) return false;
return true;
}
//combines numbers
int conNumbers(int n, int m){
string s="";
while(m!=0){
s+= to_string(m%10);
m/=10;
}
double x = pow(10, s.length());
n *= x;
//concatenate m to n
for(int i=0; i<s.length(); i++)
n+= (s[i]-'0') * pow(10, i);
return n;
}
//return nth element in fibonacci series
long long int nthFib(int smallest,int largest,int length){
long long int fib[length];
fib[0]=smallest;
fib[1]=largest;
for(int i=2;i<length;i++){
fib[i]=fib[i-1]+fib[i-2];
}
return fib[length-1];
}
//returns answer
long long int solution(int n1,int n2){
vector list1;//to store list 1, ie primes between n1 and n2
//generates prime list
for(int i=n1;i<=n2;i++)
if(isPrime(i))
list1.push_back(i);
set primeCombi; //to store combinations which are prime
for(int i=0; i<list1.size(); i++)
for(int j=0; j>n1>>n2;
cout<<solution(n1,n2);
return 0;
}
import math
n1,n2=map(int,input().split())
prime=[]
for i in range(n1,n2):
c=0
for j in range(2,i):
if(i%j==0):
c=1
if(c==0 and i!=1):
prime.append(i)
from itertools import permutations
com=[]
for i in permutations(prime,2):
s=””
s=s+str(i[0])+str(i[1])
s=int(s)
c=0
if s not in com:
for j in range(2,s):
if(s%j==0):
c=1
if(c==0):
com.append(s)
a=min(com)
b=max(com)
c=len(com)
for i in range(c-2):
d=a+b
a=b
b=d
print(d)
n1,n2=map(int,input().split())
list1=[]
for element in range(n1,n2+1):
tpm=0
if element==2:
list1.append(element)
else:
for i in range(2,element):
if element%i==0:
tpm=1
if tpm==0:
list1.append(element)
print(list1)
list2=[]
for element1 in list1:
for element2 in list1:
element1=str(element1)
element2=str(element2)
if element1!=element2:
list2.append(element1+element2)
for i in range(len(list2)):
list2[i]=int(list2[i])
print(list2)
list3=[]
for element in list2:
tpm2=0
for i in range(2,element):
if element%i==0:
tpm2+=1
if tpm2==0:
list3.append(element)
print(list3)
list4=[]
smallest=min(list3)
largest=max(list3)
count=len(list3)
a=smallest
b=largest
list4.append(a)
list4.append(b)
for i in range(count-2):
c=a+b
list4.append(c)
a=b
b=c
print(list4[len(list4)-1])
output:-
2 5
[2, 3, 5]
[23, 25, 32, 35, 52, 53]
[23, 53]
53
#pragma GCC optimize(“Ofast”)
#pragma GCC target(“avx,avx2,fma”)
#include
/* GOURAB SARKAR */
using namespace std;
typedef long long ll;
typedef long double ld;
#define PI 3.141592653589793238
#define MP make_pair
#define F first
#define S second
#define PB push_back
#define PBO pop_back()
#define permute next_permutation
#define ALL(v) v.begin(), v.end()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define ALLA(arr, sz) arr, arr + sz
#define SORTA(arr, sz) sort(ALLA(arr, sz))
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz))
#define dl “\n”
#define mm(a, val) memset(a, val, sizeof(a))
#define b_s binary_search
#define u_b upper_bound
#define l_b lower_bound
#define test \
int t; \
cin >> t; \
while (t–)
#define fast() \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);
const ld EPS = 1e-9;
const int N = 1000000005;
const ll NL = 1000000000000000005LL;
const int mod = 1e9 + 7;
const int mod1 = 1e9 + 9;
const int mod2 = 998244353;
#define fi(a, b, c) for (int a = b; a = b; –a)
#define fei(a, b, c) for (int a = b; a = b; –a) //for any particular range
#define fs(a, b) for (auto &a : b) //for loop shortcut
// inline void OPEN()
// {
// #ifdef ONLINE_JUDGE
// freopen(“input.in”, “r”, stdin);
// freopen(“output.in”, “w”, stdout);
// #endif
// }
// const int maxN = 1e5 + 1;
// vector adj[N];
// vector vis(N, false);
inline string IntToString(int a)
{
ostringstream str1;
str1 <> x;
return x;
}
const int nn = 10001;
vector prime(nn, true);
inline void P()
{
prime[0] = prime[1] = false;
for (int i = 2; i * i <= nn; i++)
{
if (prime[i])
{
for (int j = i * i; j > a >> b;
/* using sieve to generate primeno then take all combinations of that numbers the do fibonacci series –> O(n^2) and O(n) space */
vector primelist;
fi(i, a, b + 1)
{
if (prime[i])
{
primelist.PB(i);
}
}
set combNo;
int minVal = INT_MAX, maxVal = INT_MIN;
fi(i, 0, primelist.size())
{
int fstno = primelist[i];
fi(j, 0, primelist.size())
{
int scdno = primelist[j];
if (fstno != scdno)
{
string fst = IntToString(fstno);
string scd = IntToString(scdno);
fst += scd;
int noo = StringToInt(fst);
if (prime[noo])
{
minVal = min(minVal, noo);
maxVal = max(maxVal, noo);
combNo.insert(noo);
}
}
}
}
// cout << combNo.size() << dl;
// cout << minVal << " " << maxVal << dl;
ll dp[10001];
dp[0] = minVal, dp[1] = maxVal;
fi(i, 2, combNo.size() + 1)
{
dp[i] = dp[i – 1] + dp[i – 2];
}
cout << dp[combNo.size() – 1] << dl;
}
int main()
{
fast();
// OPEN();
// solve();
P();
test
{
solve();
}
return 0;
}
def prime(num):
c=0
for i in range(2,num+1):
if num%i==0:
c+=1
return c
p,q=input().split()
n=int(p)
m=int(q)
list1=[]
for i in range(n,m+1):
if prime(i)<=1:
list1.append(i)
list2=[]
for i in list1:
for j in list1:
sub=int(str(i)+str(j))
if prime(sub)<2 and sub not in list2:
list2.append(sub)
a=min(list2)
b=max(list2)
for i in range(len(list2)-2):
c=a+b
a=b
b=c
print(c,end="")