This content has been marked as final.
Show 26 replies

1. Re: Prime Number Program
807591 Apr 3, 2005 12:47 PM (in response to 807591)That program looks like you want to use a sieve algorithm (because of the boolean array).
What about that upper bound? Is the user supposed to input an upper bound between 1 and 100?
Anyway you didn't say what your problem is. 
2. Re: Prime Number Program
807591 Apr 3, 2005 2:53 PM (in response to 807591)Make a list of numbers from two to your maximum. A resizeable list would probably be the easiest to work with. Start looping through your list. For each number you come across, remove all the numbers greater than your number which are divisible by that number. In the end, you will have a list of primes.
~Cheers 

4. Re: Prime Number Program
807591 Apr 3, 2005 4:37 PM (in response to 807591)I don't see what's so difficult about it. You just need to change a few lines.
import java.io.*; public class Prime { public static void main(String args[]) throws IOException { System.out.println("Prime Numbers from 1 to 100"); BufferedReader input = new BufferedReader(new InputStreamReader(System.in)); System.out.print("Enter the primes upper bound ===>> "); final int MAX = Integer.parseInt(input.readLine()); int[] primes={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}; for(int i=0; primes<=MAX; i++)
System.out.println(primes[i]);
}
}

5. Re: Prime Number Program
807591 Apr 3, 2005 5:41 PM (in response to 807591)You forgot the spaces. And Poland.
His output format clearly needs those...//change System.out.println(primes);
//to
System.out.print(primes[i] + " ");
~Cheers 
6. Re: Prime Number Program
807591 Apr 3, 2005 8:13 PM (in response to 807591)what i actually want it to do is to let the user input an upper bound and have the program list the prime numbers up to that point. sorry for not being clear enough
thanks again 
7. Re: Prime Number Program
3004 Apr 3, 2005 8:23 PM (in response to 807591)Did you even try the last code that was posted?!? 
8. Re: Prime Number Program
807591 Apr 3, 2005 8:24 PM (in response to 3004)Did you even try the last code that was posted?!?
Did you even read it?
OP: I gave you a method that works. Did you try to implement it? What does your program look like so far, and where is it not working?
~Cheers 
9. Re: Prime Number Program
807591 Apr 3, 2005 8:48 PM (in response to 807591)Or use some initiative and do a search. The prime number algorithm is one of the basic problems that begginners are set. There would be plenty of examples all over the net. Including a recent topic in these fora. 
10. Re: Prime Number Program
807591 Apr 3, 2005 9:32 PM (in response to 807591)it was probably a mistake for me to say prime numbers between 1 and 100 because what if the user wants to input 1000? i want to have a mathematical function that determines the prime numbers instead of having them listed out
i am trying to use the sieve of erosthenes but it is giving me troubles
im trying my best to be as clear as possible because english is not my first language, please bare with me 
11. Re: Prime Number Program
807591 Apr 4, 2005 12:52 AM (in response to 807591)do you think you could write a routine
What are the divisors of a prime number?boolean prime(int x){ // this routine should return true if x is prime // your code goes here ... }
What is the relationship between modulo and divisors?
How can you use modulo to test if a number divides x?
How many numbers do you need to check if they are divisors of x before you decide x is prime?
If you could write a function that detects prime numbers, how you could you put that into a for loop to print out only the numbers that pass the prime function?
Which of those questions is the hard one? 
12. Re: Prime Number Program
807591 Apr 4, 2005 1:14 AM (in response to 807591)i am trying to use the sieve of erosthenes but it is
Do you need to use this algoritm? Can't you just use the definition of a prime number; that it's not evenly divisible by anything else but 1 and itself,
giving me troublesboolean isPrime(int N) { for (int i=2; i<N; i++) // all i from 2 to N1 if ((N%i) == 0) // N is evenly divisible by i ? return false; // yes  no prime return true; // prime }

13. Re: Prime Number Program
807591 Apr 4, 2005 2:31 AM (in response to 807591)You can test 2 as a separate case, then start i = 3 and increment by 2.
Also, you can put the stop case to i <= Math.sqrt(N). 
14. Re: Prime Number Program
807591 Apr 4, 2005 9:32 AM (in response to 807591)Here is a program that uses the sieve of Eratosthenes to find all prime numbers between 1 and 1billion. Thats about 50million prime numbers which are all stored into an array. The program needs only a few seconds on a modern PC. You can also change the program to print them out but that might take a little bit longer.
public class Prime { final static int N=50847534; final static int BUFFER=10000; public static void main(String[] argv) { int[] prim, primi; int pos, pos_prime, i, prime, prime_sqr; long time_start, time_ges; int[] buffer=new int[BUFFER]; int start, end; prim=new int[N]; primi=new int[10000]; time_start=System.currentTimeMillis(); for(i=0; i<BUFFER; i++) buffer=1;
buffer[0]=0;
prim[0]=2;
pos_prime=0;
pos=0;
start=0;
end=BUFFER*21;
for(; ;) {
while(buffer[++pos]==0);
prime=pos*2+1;
prim[++pos_prime]=prime;
i=(prime*prime)/2;
if(i>=BUFFER) break;
for(; i<BUFFER; i+=prime)
buffer[i]=0;
primi[pos_prime]=iBUFFER;
}
for(pos++; pos<BUFFER; pos++) {
if(buffer[pos]==1) {
prim[++pos_prime]=pos*2+1;
}
}
do {
pos=0; start+=BUFFER*2; end+=BUFFER*2;
for(i=0; i<BUFFER; i++) buffer[i]=1;
for(pos=1, prime=prim[pos], prime_sqr=prime*prime; prime_sqr<=end; prime=prim[++pos], prime_sqr=prime*prime) {
if(prime_sqr < start )
i=primi[pos];
else
i=(prime_sqr/2)%BUFFER;
for(; i<BUFFER; i+=prime)
buffer[i]=0;
primi[pos]=iBUFFER;
}
for(pos=0; pos<BUFFER; pos++) {
if(buffer[pos]==1) {
prim[++pos_prime]=start+pos*2+1;
if(pos_prime>=(N1)) break;
}
}
} while(pos_prime<(N1));
time_ges=System.currentTimeMillis()time_start;
System.out.println("Total number of primes found: "+(pos_prime+1));
System.out.println("Largest prime found: "+prim[pos_prime]);
System.out.println("Time: "+((double)time_ges/1000)+" seconds");
}
}