POTATOES - Editorial

PROBLEM LINK:

Practice
Contest

Author: Shalini Sah
Tester: Shiplu Hawlader and Mahbubul Hasan
Editorialist: Lalit Kundu

DIFFICULTY:

SIMPLE

PREREQUISITES:

Prime numbers

PROBLEM:

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.

AUTHOR’S AND TESTER’S SOLUTIONS:

To be updated soon.

5 Likes

Why this code is giving wrong answer while submitting. It’s running fine in my local.?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

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;	
}

}

#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;
}

why this code is giving wrong answer.Working fine on my system.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

 public static void main(String[] args) throws IOException {
       BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
       Boolean flag=true;
      
       int req=0;
    int tc = Integer.parseInt(reader.readLine());
    int g[]= new int[tc];
    for (int tt = 0; tt < tc; tt++) {
        String[] data = reader.readLine().split(" ");
        int a = Integer.parseInt(data[0]);
        int sum = Integer.parseInt(data[1]) + a;
        int total=sum;
        for(int i=1;i<31;i++)
        {total=total+1;
   
            for(int r=2;r<total;r++)
            { 
           
                if(total%r==0)
                 {
                    
                    flag=false;
                    break;
                }

            }
     
            if(flag==true)
                       
               break; 
            
             flag=true;   
        }
        req=total-sum;
        g[tt]=req;
      //  System.out.println(req);
        total=0;
          }
    for(int k=0;k<g.length;k++)
    {
        System.out.println(g[k]);
    }

}
}

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]);

cout<<first<<endl;
cout<<second;
return 0;
}

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.

why this code is giving wrong answer.Working fine on my system.

#include<stdio.h>

int main(void)
{
int x,y,z;
int n;
int i,j;
int set=0;
int *ans;
int temp,k;

  scanf("%d",&n);
  ans = (int*)malloc(n*sizeof(int));
  
  for(i=0;i<n;i++)
  {
                  scanf("%d %d",&x,&y);
                  temp = x + y;
                  for(j=1; ; j++)
                  {
                           temp = temp + 1;
                           //printf("%d\n",temp);
                           for(k=2;k<temp/2;k++)
                           {
                                                if(temp%k==0)
                                                {
                                                             set=1;
                                                             break;
                                                }
                           }
                           if(set==1) 
                           {set=0; continue; }
                           if(set==0)
                            {         *(ans+i) = j;
                                      //printf("%d\n",*(ans+i));
                                      break;
                            }                     
                  }
  }
  
  for(i=0;i<n;i++)
  {
                  printf("%d\n",*(ans+i));
  }
  
  //getch();
  return 0;

}

I am getting NZEC error.Can anyone help me code here

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

bool isPrime(int sum)
{
int count=1;
for(int i=2;i<sum/2;i++)
{
if(sum%i==0)
return false;
}
return true;
}

int main()
{
int t;
cin>>t;
for(int i=0;i<t;i++)
{
int f, s;
cin>>f>>s;
int sum=f+s+1;
while(!isPrime(sum))
sum++;

cout << sum-f-s<<endl;
}

}

why is it not working??? i am getting wrong answer

One of the simple solution to this problem is pre-computation.

Here is my code (in C)-

Link-
https://www.codechef.com/viewsolution/12622044

Commends are also included. :slight_smile:

(for those too lazy to copy paste the link-)

#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;}

}
if(m>=1){
    return 0;
}
else
return 1;

}

in (x+y+i) i will never exceed 40 since x+y <= 2000.

could any one explain me this…?

1 Like

https://www.codechef.com/viewsolution/13385218

can anyone tell me whats wrong in the above code ?
I am geeting wrong answer even though I’ve checked every thing (i think),I’ve applied fermat’s little theorem to check if the number is prime or not.

just find sum of given two integers as first and second harvest and find just next prime number , then answer will be that prime number - sum(sum of first and second harvest).

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.

1 Like

there were accepted answers that took more time than this… but this showed a TLE. please help.

thanks jawad, it solved the problem

why am i gettin wrong answer for this code?

I’ve tried most of the test cases with this code, it works fine in my local.

#include<stdio.h>
void main()
{
int t,a,b,c[1000],i=0,t1;
scanf("%d",&t);
t1=t;
while(t>0) // t test cases
{
int ct=0,p=0,j; //3 feild count
scanf("%d",&a);
scanf("%d",&b);
a+=b;
while(p!=2)
{
p=0;
ct++;
a++;
for( j=2;j<(a/2);j++)
{
if(a%j==0)
{
p=1;
}
}
if(p!=1)
{
c[i]=ct;
p=2;
i++;
}
}
t–;
}
for( i=0;i<t1;i++)
{
printf("%d\n",c[i]);
}
}

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

thanks jawad