Given x(<=1000) and y(<=1000), find the smallest z(>0) such that (x+y+z) is prime.
EXPLANATION:
Keep increasing i (starting from 1) until (x+y+i) is not prime. i will never exceed 40 since x+y <= 2000. So we can afford to check each number one by one.
To check if a number N is prime:
def check_prime(N):
for i=2 to sqrt(N):
if N%i==0:
return false
return true
Alternatively, we can use sieve of eratosthenes to check primes.
Naive primality testing (checking if N is divisible by any number from 2 to N-1) could also pass if precomputation is done.
public static void main(String[] args) throws IOException {
int x,y,sum=0;
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
StringBuilder sb = new StringBuilder();
int t = Integer.parseInt(in.readLine());
for (int i=0; i<t; i++){
StringTokenizer st = new StringTokenizer(in.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
sum=x+y+1;
boolean prime=false;
while (true){
prime = Prime(sum);
if (prime){
break;
}
sum+=1;
}
int z= sum - (x+y);
sb.append(z).append('\n');
}
out.println(sb);
out.close();
}
public static boolean Prime(int primenum){
boolean test = false;
for ( int j = 2 ; j <= Math.sqrt(primenum) ; j++ ){
if ( primenum % j == 0 ){
test = false;
break;
}
else
test = true;
}
return test;
}
Your program fails to find 2 and 3 as prime numbers. If x=1 and y=1 your program outputs 3, but the correct answer is 1. You can correct it by making value of test as true before entering loop and no need of else part within the loop.
#include <stdio.h> #include <stdlib.h> #include <math.h>
int prime(int x)
{
int n, i, flag=0;
for(i=2;i<=sqrt(x);i++)
{
if(x%i==0)
{
flag=1;
break;
}
}
if (flag==0)
return(1);
else
return(-1);
}
int main()
{
int i,j,sum,sum1,check;
long long int t;
scanf("%d",&t);
long long int x[t],y[t];
for(i=0;i<t;i++)
scanf("%lld%lld",&x[i],&y[i]);
for(i=0;i<t;i++)
{
sum=0;
sum=sum+x[i]+y[i];
for(j=1;j<10;j++)
{
sum1=0;
sum1=sum+j;
//printf("%d",sum1);
check=prime(sum1);
//printf("%d\n",check);
if (check==1)
{
printf("%d\n",j);
break;
}
else
continue;
}
}
return 0;
}
Your program fails for the input x=1326, y=1, the correct answer is 34(since 1361 is the next prime after 1327). Your program finds the answers only up to 30, make the condition of the loop in i as i<35
Why i am not gettin correct output.My code is:- #include
using namespace std;
int main()
{
int i,n,j,z[2],T;
char x[1000],y[1000];
cin>>T; //inpu test cases
for(i=0;i<T;i++)
{
cin>>x[i]; //input x and y
cin>>y[i];
}
for(i=0;i<T;i++)
{ j = 1;
n = x[i] + y[i] ;
while(j>0)
{
n = n + 1 ;
j++;
if(n%2!=0 && n%3!=0 && n%5!=0 && n%7!=0 || n==2 || n==3 || n==5 || n==7)
{
z[i] = n ;
break;
}
}
}
int first = z[0]-(x[0]+y[0]),second = z[1]-(x[1]+y[1]);
I also have a bit of problems with my code. I’m new to both Java and this website.
import java.util.Scanner;
class FindPotato {
static int primeNumber;
public static void main (String[] args) {
//Get the x and y value
Scanner inputText = new Scanner(System.in);
int x = inputText.nextInt();
int y = inputText.nextInt();
findPrime(x, y);
if (primeNumber != 0) {
int z = primeNumber -(x + y);
System.out.println(z);
}
}
/*
* Find closest prime number
* Given x, y from main method
*/
public static void findPrime (int x, int y) {
int combine = x + y;
// Restrict amount of attempts
for (int T = 1; T <= 10000; T++) {
int newNumber = x + y + T;
int i = 0;
//Count how many time a number can divide
int count = 0;
// Analyze if number is prime
while (i < newNumber) {
if (newNumber % ++i == 0) {
count ++;
// Move to next number
//if the num is not prime
if (count > 2) {
count = 0;
i = newNumber; //Exit the loop
}
}
if (i == newNumber && count == 2) {
primeNumber = newNumber;
return;
}
} //End of while loop
} // End of for-loop
} //End findPrime method
} //End class
I think the problem is probably with my input. Can someone tell me how to fix this? Thanks in advance.
#include <stdio.h>
Â
int main(void) {
// your code goes here
int t,x,y,i=0,j,count=0,flag;
int arr[700]={0}; /First 500 prime numbers should be more than enough, given the constraints.
however, we i took 700 just to be sure./
arr[0]=2;
count=1;//count is number of prime numbers in array.
for(i=3;i<7000 && count<700;i+=2)//precomputing prime numbers till 7000.
{
for(j=2;j<i;j++)
{
flag=0;
if(i%j==0)
{
flag=1;
break;
}
}
if (flag==0)
{
arr[count]=i;
count++;
}
}
scanf ("%d",&t); //inputting T
for(i=0;i<t;i++)
{
scanf ("%d %d",&x,&y);
int sum=x+y;
for (j=0; x+y>=arr[j] && j<700;j++); /*gives the smallest prime number greater than x+y.
This prime number is stored in arr[j]. Please take a moment to note the significance of '=' sign
in x+y>=arr[j]*/
int z= arr[j]-sum;
printf ("%d\n",z);
}
return 0;
Can anyone what wrong in this code
I m getting wrong answer
#include<stdio.h>
#include<math.h>
int prime(int a );
int main(){
long int n ,i ,t,x,y,z,q,g;
scanf("%ld" , &t);
while(t–){
n=0;
scanf("%ld%ld" , &x , &y);
q=x+y;
if(q==0){
printf(“not possible”);
}else
{
for(i=1; i<=41; i++){
z=q+i;
g=prime(z);
if(g){
n=i;
break;
}
}
z=0;
printf("%ld" , n);}
}
}
int prime(int a ){
int i ,m=0 ;
for(i=2; i<=sqrt(a); i++){
if(a%i==0){
m=m+1;}
