Header Ads Widget

Levy Conjecture | codechef solution

Rajnish Tripathi 08:30

 Problem Statement

Levy's conjecture, named after Hyman Levy, states that all odd integers greater than 5 can be represented as the sum of an odd prime number and an even semiprime. To put it algebraically, 2n + 1 = p + 2q always has a solution in primes p and q (not necessary to be distinct) for n > 2. (Source: Wikipedia)

In this problem, given a positive integer N (not necessary to be odd integer greater than 5). Your task is to calculate how many distinct ordered pairs (p, q) such that N = p + 2q, where p and q are primes.

Input

The first line of input contains an integer T, denoting the number of test cases. Then T test cases follow.

Each test case consists of exactly one line containing an integer N.

Constraints

  • 1 ≤ T ≤ 100000 (105)
  • 1 ≤ N ≤ 10000 (104)

Output

For each test case, output the number of ordered pairs (p, q) of primes such that N = p + 2q.

Sample 1:

Input
Output
3
2
7
11
0
1
2

Explanation:

Case #1: There are no ordered pairs (p, q) such that p + 2q = 2.

Case #2: There is only one ordered pair (p, q) = (3, 2) such that p + 2q = 7.

Case #3: There are two ordered pairs (p, q) = (7, 2), (5, 3) such that p + 2q = 11.

Code(C++):-

#include <bits/stdc++.h>
using namespace std;

void sieve(int* arr, int n)
{
arr[0]=0;
arr[1]=0;
for(int i=2; i*i<=n; ++i)
{
if(arr[i])
{
for(int j=i*i; j<=n; j += i)
arr[j]=0;
}
}
}

void solve(vector<int> &primes, vector<int> &count)
{
int n;
cin>>n;

cout<<count[n]<<endl;
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int* arr = new int[10003];
for(int i=1; i<=10001; ++i)
arr[i]=1;
sieve(arr, 10001);
vector<int> primes;
for(int i=0; i<=10001; ++i)
if(arr[i])
primes.push_back(i);
vector<int> count(100000, 0);
for(int i=0; i<primes.size(); ++i)
{
for(int j=0; j<primes.size(); ++j)
{
int val = primes[i] + 2*primes[j];
if(val<100000)
count[val]++;
}
}

int t;
cin>>t;
while(t--)
solve(primes, count);
    return 0;
}

Code(JAVA):-

import java.util.*;

/* Name of the class has to be "Main" only if the class is public. */
class codechef {

public static void main(String[] args) throws java.lang.Exception {
Scanner sc = new Scanner(System.in);
boolean arr[] = new boolean[10005];
arr[0] = false;
arr[1] = false;
for (int i = 2; i < 10005; i++) {
arr[i] = true;
}
for (int i = 2; i < 10005; i++) {
if (!arr[i]) continue;
for (int j = 2 * i; j < 10005; j += i) {
arr[j] = false;
}
}
// your code goes here
int t = sc.nextInt();
while (t != 0) {
int n = sc.nextInt();
int c=0;
for (int i = 1; i <= n; i++)
{
if(n-2*i<0) break;
if(arr[i] && arr[n-2*i])
{
c++;
}
}
System.out.println(c);
t--;
}
sc.close();
}
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-



Tags:

Post a Comment

0 Comments