Prime Number Solving Problem
I am very new at this.
Recently i got a question of making an output of prime numbers with no input involved.
class PrimeNum8{
public static void main (String [] args)
{
int num=2;
int i = 2;
int q = 1;
int term=100;
System.out.println("Prime Numbers");
if (num==2){
System.out.print(num+ " ");
}
for (int p=num; p<=term; p++){
if ((p%q==0)&& (q>=Math.sqrt(p)))
{
System.out.println(" "+p);
q++;
}
}
}//end main method
}//end class
it is pretty basic stuff for everyone out there. But its now 12am here and i've been trying to finish this from 8 pm and still with no success even going through all the forum stuff. I tried modifying what there is in the forum (most of which uses an input from user) but with no success. It's either I get all even numbers or odd numbers or every number from 2 - 100! I'm lost.
I would greatly appreciate it if someone could help me out!
Thank you...
1. Always use code tags when posting code
2. You're code isn't the easiest to read, so I'm not sure, but it seems to me like your approach is wrong. First, come up with an algorithm in pseudocode that you think should deliver the primes. Then try to implement it.
Feel free to come back with any problems you experience in the last step.
DaanSa at 2007-7-13 11:58:35 >
In addition to Daan's advice, may I suggest creating an extra method which takes an int as a parameter and returns true if that number is prime, and false if it's composite.
Your application will look like this:
public class PrimeNum8 {
public static void main (String [] args) {
int minNum = 1;
int maxNum = 25;
int primesFound = 0;
System.out.println("All primes from "+minNum+" to "+maxNum+":");
for(int p = minNum; p <= maxNum; p++) {
if(isPrime(p)) {
System.out.println("> "+p);
primesFound++;
}
}
System.out.println("Total primes found: "+primesFound);
}
private static boolean isPrime(int n) {
// for you to implement
return true;
}
}
Always use clear variable names! If you read some of your own code back in a few weeks and stumble upon a variable named q, it's likely you don't know what exactly this is.
Now do as Daan suggested: try writing down on pen and paper how you'd check a number for primality. Try translating those steps in the isPrime(...) method.
Good luck.
Thanks guys.
I was thinking of that too, but the objective of the program is to only list out the prime numbers and not the total prime numbers.
the out put should be
Prime Numbers
2 3 5 7 11
13 17 19 23 29
so on and so forth till the number 97, listing 5 prime numbers in each line. We are not allowed to use arrays. Hence, im dumfounded.
Is my condtion stament correct? I did try to list it in pseudocode, but i cant seem to get my if statement condition correct. I know that prime numbers can only be divided by itself and 1 only and that the denominator must be more or equal to the square root of the nominator. But even through the if statement i did, i still seem to get other numbers and not prime numbers alone.
If I were to post a new topic, i shall keep those tips in mind. Thank you.
> int minNum = 1;
> int maxNum = 25;
> int primesFound = 0;
> System.out.println("All primes from "+minNum+" to "+maxNum+":");
>
> for(int p = minNum; p <= maxNum; p++) {
[...]
Here's a little hack that speeds things up a bit by removing the test
for numbers that certainly aren't primes:int minNum= 2;
int maxNum= 25;
int primesFound= 0;
int[] inc= { 0, 4, 1, 2, 0, 2 };
System.out.println("All primes from "+minNum+"to "+maxNum+":");
for (int p= minNum; p*p <= maxNum; p+= inc[p%6]) {
kind regards,
Jos
JosAHa at 2007-7-13 11:58:35 >
I got this far
public class Lab8BonusQuestion {
public static void main (String [] args) {
int minNum = 1;
int maxNum = 100;
int primesFound = 0;
System.out.println("Prime Numbers");
for(int p = minNum; p <= maxNum; p++) {
if (p==2){
System.out.print(p+ " ");
}
else if((isPrime(p))&&(p>2)&&(p<13) ){
System.out.print(p + " ");
}
}
System.out.print("\n");
for(int p = minNum; p <= maxNum; p++) {
if((isPrime(p))&&(p>13)&&(p<30) ){
System.out.print(p + " ");
}
}
System.out.print("\n");
for(int p = minNum; p <= maxNum; p++) {
if((isPrime(p))&&(p>30)&&(p<50) ){
System.out.print(p + " ");
}
}
System.out.print("\n");
for(int p = minNum; p <= maxNum; p++) {
if((isPrime(p))&&(p>50)&&(p<72) ){
System.out.print(p + " ");
}
}
System.out.print("\n");
for(int p = minNum; p <= maxNum; p++) {
if((isPrime(p))&&(p>72)&&(p<99) ){
System.out.print(p + " ");
}
}
System.out.print("\n");
}
private static boolean isPrime(int n) {
for (int p=1, q=2; p<=100; p++)
if ((p%q==0)&& (q>=Math.sqrt(p)))
return true;
return false;
}
}
I separated each for loop with a \n so that there will be 5 rows.
But the output doesn't only show prime numebrs but every other number form 0 - 100.
I placed p==2 as a n if condition, because i am not sure how not too.
Again: use code tags when posting code...
I hate to say this, but your isPrime method seems totally rotten. You're not using the number passed in as a parameter. You're q variable seems to stay stuck at 2. I still don't get how you're trying to determine if a number is prime. Could be my lack of maths, or the fact that I don't get your variables.
How about this? Give your variables some more meaningful names (no p, r, or n), and post your code again, with code tags. Also include a description of the test you're trying to perform in pseudocode. Then we'll help you with any java problems.
DaanSa at 2007-7-13 11:58:35 >
sorry
by code tags you mean comment line is it?
class PrimeNum{
public static void main(String[] args) {
//declaration and initiliazation
int c = 1;
int n = 2; //prime numbers
int maxNumber=100;
//print out Prime Numbers line
System.out.println("Prime Numbers");
//loop for first line output
for ( ; (n <= maxNumber)&&(n>=1)&&(n<13); n ++)
{
//recall boolean prime number n
if (prime(n)) //if boolean output is true
{
System.out.print(n + " " );
}//end nested if recall boolean statement
}//end for loop
System.out.print("\n");// prompt to start line 2
// for loop for first line
for ( ; (n <= maxNumber)&&(n>=13)&&(n<30); n ++)
{
if (prime(n))//&& (c % 1 == 0))
{
System.out.print(n + " " );
}//end nested if recall boolean statement
}//end for loop
System.out.print("\n");//prompt to start line 3
//for loop for the third line
for ( ; (n <= maxNumber)&&(n>=30)&&(n<50); n ++) {
if (prime(n))
{
System.out.print(n + " " );
}// end nested if statement
}// end for loop for third line
System.out.print("\n");//prompt to start line 4
//for loop for the fourth line
for ( ; (n <= maxNumber)&&(n>=50)&&(n<72); n ++) {
if (prime(n))
{
System.out.print(n + " " );
}//end nested if statement
}//end for loop for fourth line
System.out.print("\n");//prompt to start line fifth and last line
//for loop for the last line
for ( ; (n <= maxNumber)&&(n>=72)&&(n<100); n ++) {
if (prime(n))
{
System.out.print(n + " " );
}//end nested if statement
}//end for loop for last line
System.out.println(); //returns carriage
}// end main method
//starts boolean method prime with argument of variable n
public static boolean prime(int n) {
for (int divisor = 2; divisor <=(n/2); divisor++)
if (n % divisor == 0)
return false;
return true;
}//end method boolean prime with argument of variable n
}//end class PrimeNum
I tried out that program and it worked
the thing is, is there anyone who can explain to me how it works?
I dont get why must we take false as the result to see wheter is it a prime number or not
why cant we use !(number%divisor==0)
it doesnt work. I tried it when i combined both methods under main.
the condition (prime(n))
could i ask? Is it to recall the method prime?
Could i make separate user defined methods to place each line? then recall it in the main method. That way, i have shorter codes right?
I dont really understand the conditions. How come, in some places, they tell me to place if(n==2)
as one of the nested if's in the for loop? Usually the program does not recognise it as a prime number. Why now it does?
I got bits and pieces from a few programs i did before and some from the net. I kinda 'paraphrased' it. Heehee.
What do you think? Is it better than before? I mean it does give me the output that I want. Is there anyway I can make it look less lines?
I think you'll solve a lot of problems if you:
a) use braces in isPrime for both the for and if statement
b) get rid of those silly printing loops. You're using "magic" numbers to figure out when to insert a line break - that's considered bad practice. Figure out a better way to insert line breaks in the right place.
And I really hate to say this, but you're last comments don't give me the impression you have any idea what you're doing. Your code reflects that. The quickest way to fix all of the issues with your code is to get somesuch idea...
DaanSa at 2007-7-13 11:58:35 >
Thank you.I will try my best to heed your suggestions.I guess I'm very very weak at doing java.
> I tried out that program and it worked the thing is, is there anyone who
> can explain to me how it works?
A bit of theory and a working method at the end: for a number n > 0 to
be prime, there should be no numbers 1 < p < n such that n%p == 0.
Another observation is that no even numbers, except 2, can be prime.
Suppose p evenly divides n, i.e. n%p == 0 and also suppose p*p > n,
then q == n/p also evenly divides n where q*q <= n.
Yet another observation is that all prime numbers, except for 2 and 3
are a multiple of 6 plus or minus 1.
The observations above can be implemented as follows:public boolean isPrime(int n) { // assume n > 1
int[] inc= { 0, 4, 1, 2, 0, 2, }
for (int p= 2; p*p <= n; p+= inc[p%6])
if (n%p == 0) return false;
return true;
}
... the inc array implements the step for the next possible prime number:
2->3->5->7->11->13->17->19->23->25->29->31->35->37->41 etc. etc.
kind regards,
Jos
JosAHa at 2007-7-13 11:58:35 >
> Thank you.
> I will try my best to heed your suggestions.
> I guess I'm very very weak at doing java.
Well, the quickest way to get stronger is to try things yourself. I.e., no "paraphrasing" things you got from the net.
@JosAH: That 6 +/- 1 was a nice one, took me a bit to prove it. And it's easier to implement than the sieve.
DaanSa at 2007-7-13 11:58:35 >
The sieve's pretty trivial if you take an OO approach. public interface IntegerSource
{
public int next();
}
public class Naturals implements IntegerSource
{
private int next = 0;
public int next()
{
return next++;
}
}
public class DivisionFilter implements IntegerSource
{
private final IntegerSource src;
private final int modulus;
public DivisionFilter(IntegerSource src, int modulus)
{
this.src = src;
this.modulus = modulus;
}
public int next()
{
int next = src.next();
while (next % modulus == 0)
{
next = src.next();
}
return next;
}
}
Next to no thought required.
> follows:> public boolean isPrime(int n) { // assume n > 1
>int[] inc= { 0, 4, 1, 2, 0, 2, }
>for (int p= 2; p*p <= n; p+= inc[p%6])
>if (n%p == 0) return false;
>return true;
> }
Sure, the code is short, but it's twice as slow as this implementation:
Also, your method returns true for 0 and 1.
private static boolean isPrime(int number) {
if (number < 2) return false;
if (number == 2) return true;
if (number % 2 == 0) return false;
if (number == 3) return true;
if (number % 3 == 0) return false;
int y = 2;
int x = (int) Math.sqrt(number);
for (int i = 5; i <= x; i += y, y = 6 - y) {
if (number % i == 0)
return false;
}
return true;
}
> > follows:> > public boolean isPrime(int n) { // assume n > 1
> >int[] inc= { 0, 4, 1, 2, 0, 2, }
> >for (int p= 2; p*p <= n; p+= inc[p%6])
> >if (n%p == 0) return false;
> >return true;
> > }
> Sure, the code is short, but it's twice as slow as this implementation:
> Also, your method returns true for 0 and 1.
Sure, but recall what I wrote: "The observations above can be
implemented as follows" ... and please take note of the comment
following the method signature.
kind regards,
Jos
JosAHa at 2007-7-20 22:06:29 >
> The sieve's pretty trivial if you take an OO
> approach. [code]public interface IntegerSource
Sure, the sieve isn't though. But you're code is already thrice as large as the example I was comparing with. And the prime's haven't been returned yet ;-) That's what I meant
DaanSa at 2007-7-20 22:06:29 >
[ code snippet snipped ]> Next to no thought required.Can I just say: elegant. I like that approach.kind regards,Jos
JosAHa at 2007-7-20 22:06:29 >
That is very elegant! You could even chain filters together... I like it.
> Can I just say: elegant. I like that approach.
Previous comment aside, I'll second this.
It seems to me though, that the example would still do every test a "dumb" prime finder would do. Am I mistaken? Mind, I'm not trying to put anything down, just further my own understanding :-)
DaanSa at 2007-7-20 22:06:29 >
> It seems to me though, that the example would still do every test a "dumb" prime finder would do. Am I mistaken?
Hard to tell. Which particular naive implementation? It's a true Erastophene's sieve, so it does trial division of each number by each smaller prime. That's better than trial division by each number up to the square root, although the increasing depth of stack means it's not necessarily faster.
It's most fun in functional programming languages. Here in SML:
datatype 'a seq = Nil
| Cons of 'a * (unit -> 'a seq);
fun filter pred Nil = Nil
| filter pred (Cons(x, xf)) =
if pred x then Cons(x, fn() => filter pred (xf()))
else filter pred (xf());
fun sift p = filter (fn n => n mod p <> 0);
fun sieve (Cons(p, nf)) = Cons(p, fn() => sieve (sift p (nf())));
fun from k = Cons(k, fn() => from (k+1));
val primes = sieve (from 2);
(* List the first 25 *)
fun take (xq, 0) = []
| take (Nil, n) = raise Subscript
| take (Cons(x, xf), n) = x :: take (xf(), n-1);
take (primes, 25);
> It's a true Erastophene's sieve, so it does trial division of each number by each smaller prime.Correction: insert ", stopping if it finds a divisor" before the full stop. Oops.
Well, I am new to this site and it looked as though you guys needed a prime finding application with no input? Well my code is stream line and pretty fast, and it can do a lot more than 2-100. But, here are the basics. If you use this code, remember to replace end with whatever number you want it to end at.
import java.util.ArrayList;
public class PrimeApp{
public static void main(String [] args){
ArrayList primes = new ArrayList();
boolean flag;
primes.add(0, new Integer(2));
for(int n = 3; n < end; n+=2){
if(n%5 != 0){
flag = true;
for(int i = 0; i < primes.size()/2&&flag; i ++){
if(n%((Integer)primes.get(i)).intValue() == 0)
flag = false;
}
if(flag)
primes.add(new Integer(n));
}
}
primes.add(0, new Integer(1));
System.out.println(primes.toString());
}
}
ahemm, 1 is not a prime number.
dwga at 2007-7-20 22:06:29 >
it is divisible by only 1 and itself, but if you really dont want it. It is easily taken out.
> it is divisible by only 1 and itself,
Yes, but still 1 is not a prime number. One of the reasons why is of the definition of a prime number, here it is: "A prime number (or prime integer, often simply called a "prime" for short) is a positive integer p > 1 that has no positive integer divisors other than 1 and p itself.".
http://mathworld.wolfram.com/PrimeNumber.html
> but if you really dont want it. It is easily taken out.
I'm pretty sure dwg knows that. You should do that for yourself if you want to generate prime numbers, because now you don't.
google "sieve of eratosthenes" and you will find efficient prime number algorithms
alta at 2007-7-20 22:06:29 >
prime number solving problem
Prime Number Solving Problem
> Prime Number Solving ProblemAnd your repeated point is?
I am trying to solve this code.131618157182424131051332311Can anyone assist?
> I am trying to solve this code.> > 131618157182424131051332311> > Can anyone assist?The answer is 42. What is your question?
> In addition to Daan's advice, may I suggest creating
> an extra method which takes an int as a parameter and
> returns true if that number is prime, and false if
> it's composite.
Back to the topic for a brief moment, may I suggest that the above is a very poor approach? It leads to an O(N*N) solution.
If you're already looping over a variable you're already doing all that's necessary to produce prime numbers. See the Sieve of Eratosthenes and numerous improvements to same, in e.g. Wirth, Djikstra, Knuth, Sedgewick, ...
ejpa at 2007-7-20 22:06:34 >
Have you see class java.math.BigInteger and methods isProbablePrime and nextProbablePrime?
When did 25 and 35 etc. become PRIME NUMBERS ?
> When did 25 and 35 etc. become PRIME NUMBERS ?Does that refer to the post that said "...the inc array implements the step for the next possible prime number..."?
