Testing all prime #'s in an if case until reaching a certain limit.
I posted this in the Algorithms forum several hours ago but no one has replied yet, so I'm going to try this one.
Hi there,
I've been working on this radical simplifier program that simplifies square roots. There is one point in the program where the code checks to see if the user entered a pure square root that is odd (9,25,49,81 etc), yet in order to properly test it, I need to somehow implement a prime # generator into the if case, and let it test each prime # unitil it gets to some big # like 1,000,000. I have comments at that certain location and have supplied both a prime # checking method and a prime # generating method. I got both methods off some free sample math code websites, and so some of their coding is a little advanced for me. Am I going about this correctly or should I code this another way? Also, any suggestions to improve it would be great. Thanks!
P.S. Hopefully my 4 space indents don't make you crazy. Sorry about that one!
import javax.swing.JOptionPane;
import java.lang.Math;
import java.awt.*;
publicclass squareRoot
{
staticint prime = 5;
staticlong root;
publicstaticvoid main(String[] args)
{
boolean calculating =true;
while (calculating)
{
String entry = JOptionPane.showInputDialog(null,
"Enter a square root to simplify.",
"Square Root Simplifier",
JOptionPane.INFORMATION_MESSAGE);
root = Long.parseLong(entry);
long testPrime = root;
long divisor = 1;
divisor = isPrime(testPrime);
if (divisor == testPrime)
JOptionPane.showMessageDialog(null,
"Your number can't be simplified any further: " + root +" is prime!",
"Square Root Simplifier",
JOptionPane.INFORMATION_MESSAGE);
else
{
if ((root % 2) == 0)//check if it's even
{
if ((Math.sqrt(root) % 2) == 0)//check if it's a pure square root
{
int square = (int)Math.sqrt(root);
JOptionPane.showMessageDialog(null,
"The square root of " + root +" is " + square,
"Square Root Simplifier",
JOptionPane.INFORMATION_MESSAGE);
}
else
{
testPrime = root;
long multiplier = 0;
while (testPrime > 0)
{
testPrime -= 2;
multiplier = testPrime;
multiplier *= multiplier;
if (multiplier < root)
{
if (multiplier == 0)
{
JOptionPane.showMessageDialog(null,
"The square root of " + root +" is already simplified!",
"Square Root Simplifier",
JOptionPane.INFORMATION_MESSAGE);
break;
}
if ((root % multiplier) == 0)
{
testPrime = root / multiplier;
multiplier = (long) Math.sqrt(multiplier);
JOptionPane.showMessageDialog(null,
"The square root of " + root +" simplified is:\n" + multiplier +" times the square root of " + testPrime,
"Square Root Simplifier",
JOptionPane.INFORMATION_MESSAGE);
break;
}
}
}
}
//calculating = false;
}
else//check if it's odd
{
while (prime <= 99999)
{
if ((Math.sqrt(root) % 3 == 0) ||//check if it's a pure square root
(Math.sqrt(root) % 5 == 0) ||
(Math.sqrt(root) % 7 == 0) ||
(Math.sqrt(root) % 11 == 0) ||
(Math.sqrt(root) % 13 == 0))
{//I notice that it always mods it by
int square = (int)Math.sqrt(root);//a prime #. How could I use
JOptionPane.showMessageDialog(null,//genPrime() to do this part?
"The square root of " + root +" is " + square,//Or is there another better way of testing
"Square Root Simplifier",//the primes?
JOptionPane.INFORMATION_MESSAGE);
break;
}
//prime = genPrime();
}
if (prime >= 99999)
{
testPrime = root;
long multiplier = 0;
while (testPrime > 0)
{
testPrime -= 3;
multiplier = testPrime;
multiplier *= multiplier;
if (multiplier < root)
{
if (multiplier == 0)
{
JOptionPane.showMessageDialog(null,
"The square root of " + root +" is already simplified!",
"Square Root Simplifier",
JOptionPane.INFORMATION_MESSAGE);
break;
}
if ((root % multiplier) == 0)
{
testPrime = root / multiplier;
multiplier = (long) Math.sqrt(multiplier);
if (multiplier == 1)
{
JOptionPane.showMessageDialog(null,
"The square root of " + root +" is already simplified!",
"Square Root Simplifier",
JOptionPane.INFORMATION_MESSAGE);
break;
}
else
{
JOptionPane.showMessageDialog(null,
"The square root of " + root +" simplified is:\n" + multiplier +" times the square root of " + testPrime,
"Square Root Simplifier",
JOptionPane.INFORMATION_MESSAGE);
break;
}
}
}
}
}
//calculating = false;
}
}
}
}
//Prime # determiner by Kevin Gong
publicstaticlong isPrime(long testPrime)
{
long test;
test = 2;// should at least use square root
while ( test < testPrime )
{
if ( testPrime % test == 0 )
return test;
if ( test == 2 )
test++;
else
test += 2;
}
return testPrime;
}
//Prime # generator
publicstaticint genPrime()
{
int [] pArray =newint[1000];//primes to check against
int i, num = 0;//num = number of primes saved
boolean check =true;
pArray[0] = 3;//store initial prime
int index = 0, test1 = 3;//first number to test is 5
while(test1 < (pArray[num] * pArray[num]) && (Math.sqrt(root) % prime == 0))
{
index = 0;
check =true;//reset flags
while(check ==true && index <= num && test1 >= (pArray[index] * pArray[index]))
{if(test1 % pArray[index] == 0)
check =false;
else index++;
}
if(check ==true)//found prime
{
if(num < (pArray.length - 1))
pArray[++num] = test1;//save prime
break;
}
test1 += 2;
//if((test1 - 1) % 100000 == 0)
//System.out.println("");//clear every 100,000
}
return test1;
}
}
[11983 byte] By [
Jason102a] at [2007-10-2 10:59:47]
When you post a second time like this, you should then add a post to your original that references this one and requests that all replies be made here.You'll irritate a few people if they end up posting duplicate replies!
Sure - I'm still new here, so thanks for letting me know.
Check out BigInteger.isProbablePrime(),have a peek at the source,go from there.
> Check out BigInteger.isProbablePrime(),> have a peek at the source,> go from there.Why not just use BigInteger's methods?(incidently, are there any other classes that permit the checking of primes)
Here, I gussied up my 8-line answer a bit so's y'all can just cut-and-paste rather than actually learn./** generate primes up to a value of n */
public static Set<Integer> genPrimes(int n)
{
int array[] = new int[n];
int i,j;
for(i=2;i<n;i++)
array[i] = i;
for(i=2;i<=n/2;i++)
for(j=i*2;j<=n;j+=i)
if(j><array.length)
array[j] = 0;
Set><Integer> primeSet = new TreeSet<Integer>();
for(int k : array)
if(k != 0)
primeSet.add(k);
return primeSet;
}
@jason:
Going through your code, I think you're not really interested in generating a random prime number, but rather generating a next prime number given a certain starting prime number.
If you input 7, then 11 should be returned, input 11 then 13 is returned, etc.
Here's an example how to do that:
public class SquareRoot {
/**
* main
*/
public static void main(String[] args) {
// testing the methods
for(int i = 1; i < 100; i++) {
if(isPrime(i)) {
System.out.println("Prime: "+i+", next prime: "+nextPrime(i));
i = nextPrime(i) + 1;
}
}
}
/**
* Check a certain number for primality.
*/
public static boolean isPrime(int number) {
if(number < 2) return false;
if(number == 2) return true;
if(number % 2 == 0) return false;
// you onlu need to go upto 'Math.sqrt(number)+1'
for(long i = 3; i < Math.sqrt(number)+1; i += 2) {
if(number % i == 0) return false;
}
return true;
}
/**
* Returns the next prime after a 'previousPrime'.
*/
public static int nextPrime(int previousPrime) {
if(previousPrime == 2) return 3;
int nextPossiblePrime = previousPrime + 2;
while(true) {
if(isPrime(nextPossiblePrime)) {
return nextPossiblePrime;
}
nextPossiblePrime += 2;
}
}
}
> @jason:
> Going through your code, I think you're not really
> interested in generating a random prime number, but
> rather generating a next prime number given a
> certain starting prime number.
> If you input 7, then 11 should be returned, input 11
> then 13 is returned, etc.
prometheuzz, you said it exactly the way I wish I said it. Yes, that's what I want my if case to test, but how would I start it at, say 1, 2, or 3, and keep checking each returned number? In another way of saying this, after it checks the next prime, how could I give it the previous one to generate the next? Is there a way to do this by using a loop or something? I really don't know of any way to loop code inside of an if case, nor can I see at the moment a way to keep calling your method outside or around the if case untill some big limit number like 1,000,000. Since you can obviously see my problem, and you understand your code better than I can, do you think you could possibly somehow implement your method into my code, and, ultimately, make it do what I wish?
Thanks to you and anybody else who will continue to help me!
Jason ^_^
> do you think you could possibly somehow implement your method into my code,I'll do it, for $85 per hour!
> you think you could possibly somehow implement your
> method into my code, and, ultimately, make it do what
> I wish?
I'm sorry, your professor explicitly told me not to do that.
; )
Please study my example carefully, and run it on your PC. Try implementing it yourself. Post questions about your implementation here.
> Thanks to you and anybody else who will continue to
> help me!
> Jason ^_^
You're welcome.
Geeezz, hahaha, very funny. How can I loop something inside a if case? It sounds ridiculus to me, and believe it or not, I tried. OK, you don't have to do it for me (that'd be nice, though :-) ), but does anyone have any suggestions on this one? Yeah, I can redo my program, but there again is something ridiculus, and I'm sure it's possible to fix it without much messing around. Gosh, maybe I should've offered some Duke Dollars or something.
> I'll do it, for $85 per hour!What an imposter!My pet monkey will do it for only €31,41and 20 banana's. I however will do it for the banana's only.
> Gosh, maybe I should've offered some Duke Dollars or something.Dukes are worth absolutely nothing, I'm afraid.
Alright, yeah, OK, I'm still terrible with my java talents, but I finally got it to work, and yes, I slapped myself for you guys for such an easy fix. This is what I have now:
while (prime <= 1000000)
{
prime = nextPrime(prime);
if (Math.sqrt(root) % prime == 0)//check if it's a pure square root
{//I notice that it always mods it by
int square = (int)Math.sqrt(root);//a prime #. How could I use
JOptionPane.showMessageDialog(null, //genPrime() to do this part?
"The square root of " + root + " is " + square,//Or is there another better way of testing
"Square Root Simplifier", //the primes?
JOptionPane.INFORMATION_MESSAGE);
break;
}
//prime = genPrime();
}
The only thing now is that if it isn't a pure root then it takes a second or so to get up to a million. Is there a better, faster way of doing this so the program doesn't pause like that?
Why hide the loop exit condition (well, one of them) within the loop? Why not have the if as part of the loop condition?
_bensmyth, thanks for that suggestion. I think now my Radical Reducer will take anything that's thrown at it. Here is how this segment of code looks now:
boolean notPure = true;
while (prime <= root)//All #'s first enter here, checking for probable pureness
{
prime = nextPrime(prime);
if (Math.sqrt(root) % prime == 0)
{
int square = (int)Math.sqrt(root);
JOptionPane.showMessageDialog(null,
"The square root of " + root + " is " + square,
"Square Root Simplifier",
JOptionPane.INFORMATION_MESSAGE);
notPure = false;
}
}
if (notPure)//All other #'s, like 45, which is 3 * the square root of 5, go here
{...}//This part already works
For anybody who's interested in the final product, I've supplied the whole code below: (Forgive the major spacing, again!) Note that I've substituted the old prime # methods with prometheuzz's code. Again, thanks a ton to everyone who contributed there thoughts on this issue. Also, I'm not going to be selling this program or anything, so feel free to use it yourself. Hopefully now this thread is done, and my next question will probably be posted in the Swing forum about a problem I have with the WindowListener stuff and its methods. Thanks again! Jason
//Written by Jason102
import javax.swing.JOptionPane;
import java.lang.Math;
import java.awt.*;
public class squareRoot
{
static int prime, root;
public static void main(String[] args)
{
boolean calculating = true;
while (calculating)
{
prime = 1;
String entry = JOptionPane.showInputDialog(null,
"Enter a square root to simplify.",
"Square Root Simplifier",
JOptionPane.INFORMATION_MESSAGE);
root = Integer.parseInt(entry);
int testPrime = root;
boolean checkPrime = false;
checkPrime = isPrime(testPrime);
if (checkPrime)
JOptionPane.showMessageDialog(null,
"Your number can't be simplified any further: " + root + " is prime!",
"Square Root Simplifier",
JOptionPane.INFORMATION_MESSAGE);
else
{
if ((root % 2) == 0)//check if it's even
{
if ((Math.sqrt(root) % 2) == 0)//check if it's a pure square root
{
int square = (int)Math.sqrt(root);
JOptionPane.showMessageDialog(null,
"The square root of " + root + " is " + square,
"Square Root Simplifier",
JOptionPane.INFORMATION_MESSAGE);
}
else
{
testPrime = root;
int multiplier = 0;
while (testPrime > 0)
{
testPrime -= 2;
multiplier = testPrime;
multiplier *= multiplier;
if (multiplier < root)
{
if (multiplier == 0)
{
JOptionPane.showMessageDialog(null,
"The square root of " + root + " is already simplified!",
"Square Root Simplifier",
JOptionPane.INFORMATION_MESSAGE);
break;
}
if ((root % multiplier) == 0)
{
testPrime = root / multiplier;
multiplier = (int) Math.sqrt(multiplier);
JOptionPane.showMessageDialog(null,
"The square root of " + root + " simplified is:\n" + multiplier + " times the square root of " + testPrime,
"Square Root Simplifier",
JOptionPane.INFORMATION_MESSAGE);
break;
}
}
}
}
//calculating = false;
}
else //check if it's odd
{
boolean notPure = true;
while (prime <= root)
{
prime = nextPrime(prime);
if (Math.sqrt(root) % prime == 0)//check if it's a pure square root
{
int square = (int)Math.sqrt(root);
JOptionPane.showMessageDialog(null,
"The square root of " + root + " is " + square,
"Square Root Simplifier",
JOptionPane.INFORMATION_MESSAGE);
notPure = false;
}
}
if (notPure)
{
testPrime = root;
int multiplier = 0;
while (testPrime > 0)
{
testPrime -= 3;
multiplier = testPrime;
multiplier *= multiplier;
if (multiplier < root)
{
if (multiplier == 0)
{
JOptionPane.showMessageDialog(null,
"The square root of " + root + " is already simplified!",
"Square Root Simplifier",
JOptionPane.INFORMATION_MESSAGE);
break;
}
if ((root % multiplier) == 0)
{
testPrime = root / multiplier;
multiplier = (int) Math.sqrt(multiplier);
if (multiplier == 1)
{
JOptionPane.showMessageDialog(null,
"The square root of " + root + " is already simplified!",
"Square Root Simplifier",
JOptionPane.INFORMATION_MESSAGE);
break;
}
else
{
JOptionPane.showMessageDialog(null,
"The square root of " + root + " simplified is:\n" + multiplier + " times the square root of " + testPrime,
"Square Root Simplifier",
JOptionPane.INFORMATION_MESSAGE);
break;
}
}
}
}
}
//calculating = false;
}
}
}
}
/**
* Check a certain number for primality.
*/
public static boolean isPrime(int number) {
if(number < 2) return false;
if(number == 2) return true;
if(number % 2 == 0) return false;
// you only need to go upto 'Math.sqrt(number)+1'
for(long i = 3; i < Math.sqrt(number)+1; i += 2) {
if(number % i == 0) return false;
}
return true;
}
/**
* Returns the next prime after a 'previousPrime'.
*/
public static int nextPrime(int previousPrime) {
if(previousPrime == 2) return 3;
int nextPossiblePrime = previousPrime + 2;
while(true) {
if(isPrime(nextPossiblePrime)) {
return nextPossiblePrime;
}
nextPossiblePrime += 2;
}
}
}
