Consecutive Primes Solution Google Kickstart 2021

Table of Contents

Problem

Ada has bought a secret present for her friend John. In order to open the present, Ada wants John to crack a secret code. She decides to give him a hint to make things simple for him. She tells him that the secret code is a number that can be formed by taking the product of two consecutive prime numbers, such that it is the largest number that is smaller than or equal to ZZ. Given the value of ZZ, help John to determine the secret code.

Formally, let the order of prime numbers 2,3,5,7,11,2,3,5,7,11, … be denoted by p1,p2,p3,p4,p5,p1,p2,p3,p4,p5, … and so on. Consider RiRi to be the product of two consecutive primes pipi and pi+1pi+1. The secret code is the largest RjRj such that Rj≤ZRj≤Z.

Input

The first line of the input gives the number of test cases, TT. TT lines follow.
Each line contains a single integer ZZ, representing the number provided by Ada as part of the hint.

Output

For each test case, output one line containing Case #xx: yy, where xx is the test case number (starting from 1) and yy is the secret code – the largest number less than or equal to ZZ that is the product of two consecutive prime numbers.

Limits

Time limit: 15 seconds.
Memory limit: 1 GB.
1≤T≤1001≤T≤100.

Test Set 1

6≤Z≤20216≤Z≤2021.

Test Set 2

6≤Z≤1096≤Z≤109.

Test Set 3

6≤Z≤10186≤Z≤1018.

Sample

Sample Input

2
2021
2020

Sample Output

Case #1: 2021
Case #2: 1763

For Sample Case #1, the secret code is 20212021 because it is exactly the product of consecutive primes 4343 and 4747.

For Sample Case #2, the secret code is 17631763 because the product of 4141 and 4343 is 17631763 which is smaller than 20202020, but the product of 4343 and 4747 exceeds the given value of 20202020.

Also Read:

Solution:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1000005;
const ll MOD = 1000000007;
const ll INF = 0x3f3f3f3f3f3f3f3f;

bool isPrime(ll a){
if(a == 1) return 0;
if(a == 2) return 1;
if(a % 2 == 0) return 0;
for(ll i = 3; i * i <= a; i += 2)
if(a % i == 0) return 0;
return 1;
}

void go(){
ll z;
cin>>z;
if(z < 15){ cout<<6<<‘\n’; return; } ll sq = 0; for(ll i = 30; i >= 0; –i)
if((sq + (1LL << i)) * (sq + (1LL << i)) <= z)
sq += (1LL << i);
ll p2 = sq;
while(isPrime(p2) == 0)
–p2;
ll p3 = sq + 1;
while(isPrime(p3) == 0)
++p3;
if(p2 * p3 <= z){
cout<<p2 * p3<<‘\n’;
return;
}
ll p1 = p2 – 1;
while(isPrime(p1) == 0)
–p1;
cout<<p1 * p2<<‘\n’;
}

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int tt;
cin>>tt;



for(int i = 1; i <= tt; ++i){
    cout<<"Case #"<<i<<": ";
    go();
}

}

Consecutive Primes Solution Google Kickstart 2021