|
-
Nov 21st, 2005, 06:13 PM
#1
Thread Starter
Fanatic Member
Finding prime numbers
I have this code as an implementation of the 'Sieve of Eratosthenes'. But either it is super duper slow or it doesn't work. What is wrong with it?
p.s. I am finding all the primes numbers in a sorted array with numbers 1-100 inclusive.
Code:
public void sievePrimes()
{
numbers[0] = 0;
int n = numbers[99];
for(int i=1; i<n; i++)
{
numbers[i] = 1;
}
int p = 2;
while(p*p <= n)
{
int j = p*p;
while(j <=n)
{
numbers[j-1] = 0;
j = j+p;
}
while(numbers[p] != 1)
{
p++;
}
}
for(int index=0; index < numbers.length; index++)
{
System.out.println(numbers[index]);
}
}
Last edited by x-ice; Feb 25th, 2007 at 07:27 PM.
-
Nov 22nd, 2005, 12:06 AM
#2
Re: Finding prime numbers
while (j <= n) {
numbers[j - 1] = 0;
j = j + p;
}
Doesn't stop looping
"I'm not normally a praying man, but if you're up there, save me... Superman!" - Homer Simpson
My Blog
-
Nov 22nd, 2005, 04:36 AM
#3
Thread Starter
Fanatic Member
Re: Finding prime numbers
 Originally Posted by ComputerJy
while (j <= n) {
numbers[j - 1] = 0;
j = j + p;
}
Doesn't stop looping
How can i stop it from doing that and work correctly?
Last edited by x-ice; Nov 22nd, 2005 at 04:40 AM.
-
Nov 22nd, 2005, 04:41 AM
#4
Thread Starter
Fanatic Member
Re: Finding prime numbers
This is the psuedo code algorithm.
Code:
Eratosthenes(n) {
a[1] := 0
for i := 2 to n do a[i] := 1
p := 2
while p2 < n do {
j := p2
while (j < n) do {
a[j] := 0
j := j+p
}
repeat p := p+1 until a[p] = 1
}
return(a)
}
-
Nov 22nd, 2005, 12:41 PM
#5
Re: Finding prime numbers
This is the algorithm as I know it:
Code:
public class Sieve {
private static int upperLimit = 1000;
private static boolean[] flags;
public Sieve() {}
public static void main(String[] args) {
initialize(args);
findPrimes();
displayPrimes();
}
private static void initialize(String[] args) {
if (args.length > 0) {
upperLimit = Integer.parseInt(args[0]);
}
flags = new boolean[upperLimit + 1];
for (int position = 0; position <= upperLimit; position++) {
flags[position] = false;
}
}
private static void findPrimes() {
for (int position = 2; position <= Math.sqrt(upperLimit); position++) {
if (!flags[position]) {
int multiple = position * 2;
while (multiple <= upperLimit) {
flags[multiple] = true;
multiple += position;
}
}
}
}
private static void displayPrimes() {
for (int position = 2; position <= upperLimit; position++) {
if (!flags[position]) {
System.out.print(position + ", ");
}
}
}
}
"I'm not normally a praying man, but if you're up there, save me... Superman!" - Homer Simpson
My Blog
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|