Tom's Guide | Tom's Hardware | Tom's Games
 |
 |
 |
I am new to Java and I am working on a program where a user enters an integer(n) and then the first prime number larger than the integer(n) is calculated and printed. I found how to input and ouput the information, but I do not know how to calculate it. Any help is greatly appreciated.
To figure out the prime number, you're going to have to go *waaay* back to prealgebra (maybe not that far, depending on how old you are) and review a basic definition of a prime number (at least, this is how I describe it) - a prime number is any whole number in which no previous whole number can be divided evenly into it. Basically, that means that for any whole number n, there can be no whole number w that divides into it evenly.
In Java, this would probably look something like:
static public IsPrime(int number)
{
if (number == 1 || number == 2)
return 1;
for (int i=2; i<(int)(number/2); i++)//assumes number is unsigned...I don't even know that you *can* have unsigned numbers in Java...in either case, I'm sure there's a Math.abs() or something similar that you could use
{
if ( (number/i)==(int)(number/i) )
return 0;
}
return 1;
}..or something like that. I make really stupid mistakes when I'm really tired, so I wouldn't rely on that too thoroughly...
Also, it should be noted that this is by no means the fastest way to find a prime number. There are much faster algorithms, but this was the simplest one I could think of...Hope that helps!
AKhalifman@hotmail.com
0 
In fact, it's likely that that Math class I talked about earlier comes with a method to determine whether or not a number is prime, and it's probably much faster than the simple example I gave (whose method, I just realized, doesn't even have a return type O_o...also, I think Java uses true and false). Being a C++ man myself (you couldn't tell?), I have little to no knowledge of java classes, so this would be a good topic to google (or wait for someone less lazy to reply).
AKhalifman@hotmail.com
0
if you want something really sophisticated, you will need to:
- test that the next number does not end in a 0, 2, 4, 5, 6, or an 8 => otherwise pick the next number
- if your number ends in a 1, 3, 7 or 9, you can test to see if the numbers 2, 3, 4, 5, ... go into it up until the square root of that number for example, to test whether 101 is prime, you will need test division by 2, 3, 4, 5, 6, 7, 8, 9, 10 as 10 is roughly the square root of 101
for small numbers, the ideas above won't make much difference but for very large numbers they will
serge
0
There is no method to determine that a number is prime except by trial division. There are plenty of probabilistic methods that check compositeness and can tell you if a number is definitely not prime but trial division is the right method for small integers anyway. If the user inputs an odd number n (if not, just add 1) then you only need to check for divisibility by numbers in the range (3,[sqrt(n)]),(3,[sqrt(n+2)]),... where [.] means greatest integer not greater than (casting to an int should work).
You shouldn't have any problem implementing this in Java as an infinite outer loop starting at the inputted number and an inner loop not too different to BlueRaja's ;-) but please don't return 1 as a prime number - it is not! (Historically it has been considered prime but apart from that messing up the "fundamental theorem of arithmetic", it looks even worse in the more general number fields if units are considered prime.
0
class getNextPrime {
public static long input,root;
public static boolean isPrime;
public static void main(String[] args) {
try { input=Long.parseLong(args[0]); }
catch (NumberFormatException nfx) {
System.out.println("Couldn't make your string into an integer");
System.exit(1); }
if (input<=2) {
System.out.println(2);
System.exit(0); }
for (int k=3;k<9;k+=2) {
if (input<=k) {
System.out.println(k);
System.exit(0); } }
if (input == ((input >> 1) << 1)) { input+=1; }
for (long i=input;;i+=2) {
root=(long)Math.sqrt(i);
for (long j=3;j<=root;j++) {
if (i == (long)(i/j)*j) {
isPrime=false;
break; }
if (j==root) { isPrime=true; } }
if (isPrime==true) {
System.out.println(i);
break; } } } }The above code works quickly enough on my machine for input less than around 10^15. It also worked easily quickly enough for ints instead of longs (Java doesn't seem to have unsigned types - only ints up to 2^31-1 and longs up to 2^63-1). That is quite interesting because most primality testers use a sieve or a precomputed array to set up a table of primes for an initial pass of trial divisions or simple inequality tests followed by one or more strong probable prime (SPP) tests which are then combined with known facts about the natural numbers up to certain limits that can guarantee a SPP is in fact prime. The largest of these limits I've seen recently is only about 7/2 x 10^14 and beyond such a limit, the programme cannot guarantee primality.
Using these methods would be faster than trial division in any case but if you find that your machine is not too slow at trial division beyond the limit of certainty it may well be worth using it. If you only care about having a number that is probably prime in a Java programme and you don't want to write your own SPP tests then you can use the java.math.BigInteger isProbablePrime method. I didn't try using the BigInteger class for trial divisions since there is no [square root] method and it's unpleasant and less efficient to use Java compared to the C/C++ gmp library for example. If you are intending to make a more capable and efficient primality tester (even if it has to be in Java) and want to know more about SPP testing just ask.
0
You should add:
if (input > 9223372036854775783L) {
System.out.println("Number out of range");
System.exit(1); }just after the catch block since although 2^31-1 is prime and the code worked for ints, 2^63-1 is not and changing to longs introduced a bug.
0
class getNextPrime {
public static long input,root;
public static boolean isPrime=false;
public static void main(String[] args) {
try { input=Long.parseLong(args[0]); }
catch (NumberFormatException nfx) {
System.out.println("Couldn't make your string into an integer");
System.exit(1); }
if (input > 9223372036854775783L) {
System.out.println("Number out of range");
System.exit(1); }
if (input<=2) {
System.out.println(2);
System.exit(0); }
for (int k=3;k<9;k+=2) {
if (input<=k) {
System.out.println(k);
System.exit(0); } }
if (input%2 == 0) { input+=1; }
for (long i=input;;i+=2) {
root=(long)Math.sqrt(i);
for (long j=3;j<=root;j+=2) {
if (i%j == 0) { break; }
if ((root-j) <= 1) { isPrime=true; } }
if (isPrime==true) {
System.out.println(i);
break; } } } }This is somewhat faster now that it doesn't waste time dividing by even numbers %-6
0
First, find primes here.
Woldbone:
I think your code might be flawed.
Try entering the number 45698875 (just a random one I tested). Your program says this is prime, when in fact it is not. This is one among many incorrect assesments it gave me.
Looking at your code I'm not sure why you did some of what have. For example, what's the purpose of this?
if (input%2 == 0)
input+=1;2 is the only even prime number. Also, why would you want to modify the user's input? That would seem like a very big no-no.
Also, and I haven't looked at it real closely, but those nested for loops are pretty interesting. What method are you trying to use to determine if the number is prime? I've got to think that by modifying input you've pretty much borked the entire problem.
Here's what I came up with. Not the fastest or best way to do it maybe (see that website linked to above for better) but it works. I had it output of the execution time for kicks.
==========================================================
class IsPrime2
{
public static void main(String[] args)
{
boolean isPrime = true;
long input = 0, start, end;start = System.currentTimeMillis();
try
{
input=Long.parseLong(args[0]);
}
catch (NumberFormatException e)
{
System.out.println("Error parsing input: number too large or invalid number.");
System.exit(1);
}if (input < 2 || (input % 2 == 0))
isPrime = false;if (input == 2)
isPrime = true;
if (isPrime)
for (int i=3; i<=(input/2); i+=2)
if (input % i == 0)
{
isPrime = false;
break;
}if (isPrime == true)
System.out.println(input + " is a prime number.");
else
System.out.println(input + " is NOT a prime number.");end = System.currentTimeMillis();
System.out.println("\nExecution time: " + (end-start) + " milliseconds.\n");
}
}On my system it takes about 2 seconds to test a prime number around 50,000,000, but numbers near 1 billion take close to a minute. This is an impractical way to test large numbers, but demonstrates both a simple understanding of Java and prime numbers.
0
"I think your code might be flawed."
My bugs aren't that bad! Maybe you've copied the code wrongly or you did not look closely at the output Doc:
$ time java getNextPrime 45698875
45698881real 0m0.113s
user 0m0.099s
sys 0m0.007s$ factor 45698881
45698881: 45698881"Looking at your code I'm not sure why you did some of what have"
The code is very simple but it would probably help comprehension if you had been trying to solve the same problem with your own code!
Anyway; the purpose of adding one to the user's input if it's an even number is to cut out some of the work from the outset. We're looking for the next largest prime not just testing the input for primality and then stopping so we want to start with the nearest odd integer >= the user's input and increment by 2 until we find a prime. I would've thought that would be clear from a cursory contemplation of the differences between the class names "getNextPrime" and "IsPrime2"
I should point out that your testing up to input/2 is a performance hit when the number is in fact a prime and there must be one - in my programme at least.
"What method are you trying to use to determine if the number is prime? "
I believe it is known as trial division and I'm sure I mentioned it before ;-)
"I've got to think that by modifying input you've pretty much borked the entire problem."
Heh! - Well if I was simply trying to test the user's input for primality, it would be an emborkation of that particular problem - yes. However, solving that problem would itself be to bork the original problem as described by Dave!
"On my system it takes about 2 seconds to test a prime number around 50,000,000, but numbers near 1 billion take close to a minute. This is an impractical way to test large numbers, but demonstrates both a simple understanding of Java and prime numbers."
time java getNextPrime 1000000000000000
1000000000000037real 0m2.174s
user 0m2.140s
sys 0m0.011sOf course a million billion is not really a large number but longs don't hold large integers anyway and 2 seconds isn't unacceptable. As I've previously explained; Java isn't the best tool to use for number theory from what I have seen - which is why I have the gmp library, pari and other tools, and trial division isn't the way to test for primality of integers if you can avoid it but you cannot always do so.
0
s/performance hit/huge performance hit/
$ time java IsPrime2 1000000007
1000000007 is a prime number.Execution time: 45836 milliseconds.
real 0m45.991s
user 0m45.538s
sys 0m0.017s$ time java getNextPrime 1000000007
1000000007real 0m0.118s
user 0m0.098s
sys 0m0.010s
0
NP Doc. :) - I thought this was potentially one of the less dull questions in this forum and I was interested to see what Java could do. It's good to see someone else taking an interest too.
0
Thanks for all the help, that's a very interesting method of finding the prime number.
I will have to follow step by step to see how it actually works.
0
My original post was only meant to show how to test for a prime number, as I felt it wrong to do the assignment for him/her...
AKhalifman@hotmail.com
0
You may be right Blue but it was my first Java programme too so I don't feel too badly about it. There's plenty of room for improvement in the code and knowing what I know now I certainly wouldn't hand in the POS above in for marking but trivial trial division is essentially the only solution at this level and I don't think writing a loop that divides one number by another is giving much away!
0
import java.util.Random;
public class s5ex1 {
public static void main(String[] args) {Random r=new Random();
int a=r.nextInt();
if (a%2==0){
System.out.println("numero "+a+" nao é primo");
}
else {
int b=a;
int c=b+20;
while (b<c){if (a%b==0 && a%a==0){
System.out.println("numero "+a+" é primo");
break;
}
else {
b=b+1;
}}
if (b>=c){
System.out.println("numero "+a+" nao é primo");
}this works well only change the portuguese text to english :P if any bugs let me now.. it worked for what i wanted
0  |
 |
 |
This post is quite old and has been locked from receiving new replies. Please create a new posting instead.
| Ads by Google |
