Feb 2011
1 / 23
Feb 2011
Mar 2016
mr_phobos
Feb '11

Hi all,
I have an algorithm for this problem (code PRIME1). It runs reasonably fast, but I'm still getting "wrong answer". I tried to test the code many times on different inputs and I'm unable to figure out, where the problem is.

I submit the solution as JAR.

The code of main "main" method is here:

public static void main(String[] args) {
        PrimeGenerator generator = new PrimeGenerator();

    try {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int numberOfTests = Integer.valueOf(in.readLine());

        boolean first = true;
        for(int i = 0; i < numberOfTests; i++) {
            String[] interval = in.readLine().split(" ");

            if(! first )
                System.out.println("");
            else
                first = false;

            generator.printInterval(Integer.valueOf(interval[0]),
                    Integer.valueOf(interval[1]) );
        }
    } catch(IOException e) { }
}

Can anyone see a problem here? The algorithm itself is hidden in the PrimeGenerator class - but I do believe, that it works fine. I there might be a problem with parsing the input or producing the output.

Also, if you've got some test inputs, I'd like to see them. I have found couple of test inputs on this forum, but it looks like the code works fine for those inputs.

Thanks a lot

Tony

leppyr64
Feb '11

You'll have to post the rest of your code. There's nothing wrong with what you have posted but it's impossible to come up with a test case. The main issue is likely with prime numbers greater than yor threshold.

mr_phobos
Feb '11

Ok

removed code

Note that I have tested the program on many intervals. For instance it gives 4832 between 999900000 and 1000000000 - which should be correct according to this forum. I also tried more intervals in one run - again correct answers. I tried both small and big primes. I verified the big primes using prime-numbers.org. I also tried intervals, which started and/or ended with primes.

Any help will be highly appreciated.

I've got one suggestion - if I may. It might be a good idea to provide a test case for such a problems. I understand, that you can't provide us with the same test you use to verify the correctness. But you could provide us with a different test case with similar complexity - so, if the program passes this test case, it's highly probable, that it also passes the "ultimate" tests.

leppyr64
Feb '11

We can't run this code. Please post it in one block as you would if you were submitting it to the judge. That way we can debug the actual issue.

This takes all of the difficulty out of "solving" the problem. Granted there are many problems that need a few more test cases because they ones they have posted are useless but in general it should be the responsibility of the solver to determine the "useful" test cases.

mr_phobos
Feb '11

Here it is:

removed code

Works in ideone.com

Thanks for any ideas

mr_phobos
Feb '11

Maybe one question. Is it considered to be an error, if I produce trailing "\n" characters for some inputs?

Thanks

mr_phobos
Feb '11

Thanks a lot - I'll fix the code as soon as I can. Hopefully, it was the only problem smile

mr_phobos
Mar '11

Finally, solution accepted smile

Feel free to delete this thread or it's parts.

Thanks a lot

leppyr64
Mar '11

Cheers!

In future please remove your own code after getting AC.

Also, if you read the BBOne tutorial in the Problemset Archive section, you'll find that the BBOne tag functions just like a posting to Ideone. It's really quite useful because anyone who can get to the forum can execute your code right on the forum.

4 years later
miche_atucha
Jan '16

I´m also getting 4832 primes between 999_900_000 and 1_000_000_000 but still, wrong answer, any other range with primes amoun to compare?
Thanks in advance!

leppyr64
Jan '16

We could post test cases but it would be a waste of our time because they would probably be successful and then our work would have been for nothing. Please post your code.

red_hat
Jan '16
3

Hello guys.
Here's my code.
I am getting a time limit exceeded error but it works fine on ideone and even on my system sweat .
Could i get any suggestions or please post any test cases so that i can check it myself?

#include <iostream>
using namespace std;

int main() {
	
	// your code here
	long int in;
	cin>>in;
	while(in>0)
	{
		long int n1,n2;
		cin>>n1>>n2;
		long int x=n1;
		while(x<=n2)
		{
			if(x%2==0 && x!=2 || x==1)
			{
				x++;
			}
			else
			{
				int c=0;
				for(long int i=3;i<x/2;i++)
				{
					if(x%i==0)
					{
						c++;
						break;
					}
				}
				if(c==0)
				{
					cout<<x<<'\n';
				}
				x++;
			}
			
		}
		cout<<'\n';
		in--;
	}
	return 0;
}
red_hat
Jan '16

Okay i get it.I am a beginner so could you advise on what kind of algorithm to use?

daft_wullie
Jan '16

There is no need to use another algorithm for this problem. But your code checks more divisors than it has to. It is not necessary to check divisors up to x/2.

red_hat
Jan '16
2

Thanks daft_wullie.
Modified the code as you said.
Now it's WA and for the reference am getting 4832 primes between 999,900,000 and 1,000,000,000.

Here's the code..

include

include

using namespace std;

int main() {

// your code here
long int in;
cin>>in;
while(in>0)
{
	long int n1,n2;
	cin>>n1>>n2;
	long int x=n1;
	while(x<=n2)
	{
		if(x%2==0 && x!=2 || x==1)
		{
			x++;
		}
		else
		{
			int c=0;
			for(long int i=3;i<=sqrt(x);i+=2)
			{
				if(x%i==0)
				{
					c++;
					break;
				}
			}
			if(c==0)
			{
				cout<<x<<'\n';
			}
			x+=2
			;
		}

	}
	cout<<'\n';
	in--;
}
return 0;

}

28 days later
ullas99
Feb '16

package com.spoj;

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Universe {

public void universe()
{
	List<Integer> list = new ArrayList<Integer>();
	Scanner sc = new Scanner(System.in);
	while(true)
	{
		System.out.println();
		int val = sc.nextInt();
		if(val == 42)
		{
			break;
		}
		System.out.println(val);
		list.add(val);
	}
}

public void primeNumberRange() 
{
	//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	Scanner sc = new Scanner(System.in);
	System.out.println();
	int testCase = 0;
	testCase = Integer.parseInt(sc.next());
	System.out.println(testCase);
	String[] rangeArr = new String[testCase];
	int index = 0;

	Scanner sc1 = new Scanner(System.in);
	while(testCase > 0)
	{
		System.out.println();
		String rangeString = null;;
		rangeString =sc1.nextLine();
		rangeArr[index] = rangeString;
		++index;
		--testCase;
	}
	sc.close();
	sc1.close();
	for(int i=0;i<rangeArr.length;i++)
	{
		String[] ranges = rangeArr[i].split("\\s+");
		int lowerRange = Integer.parseInt(ranges[0]);
		int upperRange = Integer.parseInt(ranges[1]);
		List<Integer> primeNumbers = new ArrayList<Integer>();

		primeNumbers.add(2);
		primeNumbers.add(3);

		for(int num=lowerRange ; num <= upperRange;num++)
		{
			int sqrt = (new Double(Math.sqrt(num))).intValue();
			boolean notPrime = false;
			for(Integer prime : primeNumbers)
			{

				if(num ==1 || sqrt == 1)
				{
					notPrime = true;
					break;
				}					
				else if((num != prime && num % prime == 0))
				{
					notPrime =true;
					break;
				}						
			}
			if(!notPrime && (num !=2 || num !=3))
			{
				//System.out.println(num);
				primeNumbers.add(num);
			}
		}
		for(Integer primes :primeNumbers)
		{
			System.out.println(primes);
		}
			System.out.println();
	}

}

public static void main(String[] args)
{
	Universe uv = new Universe();
	uv.primeNumberRange();
}

}

It shows runtime error when submitted