Gettign prime numbers
Hi, having problems implementing the sieve of eratosthenes
publicvoid prime()
{
int a;
int[] v =newint[100];
int sqr;
int total = 900;
int index;
index = 0 ;
int[] hold =newint[100];
for(int p = 0; p == 100; p++)
{
hold[p] = Numbers[p];
}
int r = 2;
sqr = r * r;
for(int i=2; sqr > total; i++)
{
sqr = i * i;
for(index = 0; index > total / 2; index++)
{
v[i] = i * hold[index];
}
// loop that goes through Numbers, and compares to v. if its in v and in numbers dont print it
for(index = 0; index == 100; index++)
{
for(int g = 0; g == 100; g++)
{
if(hold[index] == v[g])
{
System.out.println("This is not a prime number: " + hold[index]);
}
}
}
for(int tracker = 0; tracker == 100; tracker++)
{
// System.out.println(hold[tracker]);
}
}
}
basically wont display anything.
[2326 byte] By [
Titanium] at [2007-9-30 20:50:03]
> for(int p = 0; p == 100; p++)
Let's take just one of your loops, like the above. It says:
1) initialize p to 0
2) while p equals 100 do this loop
See the problem? It doesn't equal 100 to start with, so it never enters the loop.
How about:
p <= 100
(and actually, you want p < 100)
it hasnt helped at all. It stil lisnt doing anything.
Am i going about it the right way? To me the code seems to be fine, however it isnt producing ANY results, what so ever. Could anyone suggest another approach
> it hasnt helped at all. It stil lisnt doing anything.I see. You aren't willing to try things out and post specific problems - you want someone to just take all your code and fix it and give you the complete solution. Well, good luck with that.
> To me the code seems to be fine, however it isnt producing ANY results, what so ever.How many times is each loop being executed?
> it hasnt helped at all. It stil lisnt doing anything.Did you correct all the instances of that error, or only the one that warnerja pointed out?
And in case it didn't occur to you,for(int i=2; sqr > total; i++)also has the loop test backwards.
all of your for loops are SHIT.thats the nicest way I can put it.
it tests it bckwards because its sorted so that the highest number is first in the list (which needs to stay that way). All instances of the error were corrected appropriatly. And i dont know where the problem lies. Hence i posted all of my code!
ok...please post your new code
Some suggestions:* Don't write the complete program at once.* Work your solution out on paper first, then code (parts of) it.* Don't ignore advice.
public void prime()
{
int[] hold = new int[100];
ArrayList lists = new ArrayList();
readData();
sort();
for(int i=0; i<100; i++)
{
hold[i] = Numbers[i];
}
lists.add(hold[0]);
for(int i = 1; i < 100; i++)
{
Integer temp = new Integer(hold[i]);
lists.add(temp);
for(int j = i; j < 100; j++)
{
if(hold[j] % i == 0) // not going past the number 2
{
hold[j] = 0;
}
}
}
for(int c = 0; c <99; c++)
{
System.out.print(lists.get(c));
}
}
Is what i have now, after some re-adjustments. It seems to think every number after 2 isnt prime, i think its because of the if(hold[j] % i == 0) Which should go the the number in the array, divide it by all numbers from 1 to 100, and if it has a remainder 0. i.e. it is divisable by without remainder and there is a prime. Any suggestions?
Where do you initialise Numbers, and to what?
And (I scanned through your code) why do you use so many arrays? You can do it with one, you know.
What exactly is your assignment? Do you need to use the "sieve of eratosthenes" system or are you just trying to get primes?
the program reads in 100 integers 1-100 froma file, (readData()), then sorts them (sort()) then uses the sieve of erathneses to get the prime numbers from them, all arrays exterior are initialised.
i need to keep the other array intact, the hold one is used just as a medium, the actual primes are added to an Arraylist
You're ending up setting every element of your hold[] to 0.
Stick some sysout's in there to try and see what's happening. Here's a good place to start
for(int j = i; j < 100; j++) {
System.out.println("hold[j] " + hold[j]);
if(hold[j] % i == 0) {
hold[j] = 0;
}
}
and you can replace the for loop you're using to set hold[] with one line.
hold = numbers;
> All instances of the error were
> corrected appropriatly. And i dont know where the
> problem lies. Hence i posted all of my code!
You posted some code. Some changes were suggested. You said you made them. Now what you have doesn't work, but we don't know what it looks like.
> it tests it bckwards because its sorted
If you want to read an array backwards, rather than forwards, then you don't do that by using a terminating condition that is never true. You do it by starting at the end and moving towards the beginning. However I think it would be better to use the standard array loopfor (int i=0; i<array.length; i++)
for a start. Then look at the three pieces of that and understand what they do: The first one (i=0) tells the loop where to start. The third one (i++) tells the loop what to do in order to move on to the "next" entry. And the second one (i><array.length) tells the loop when it's okay to move on to the "next" entry.>
but what is entirely more fascinating is how to get prime ribnow that... is a real conundrum.
> how to get prime rib> now that... is a real conundrum.Not with a sieve, that's for sure. Use a butcher knife to remove all the composite ribs.
A Sieve of E finds primes in a consecutive sequence of integers like all numbers between 0 and 100
Your problem is to find primes in sorted list of ints which may not be consecutive, so at best it is a
modified Sieve algorithm you need to use.
I am not posting any code, you still have to think about the problem however I will give you some tips about
solving the problem without giving you any hints on how to code it.
Back to basics: A Prime number is defined as being any positive integer that is only divisible by itself and 1.
There is a well known process for finding common integer denonimators of a number, 4 has denominators 4, 2 and 1 for instance so 4 is not a prime number.
You need to find the greatest common denominator for each integer you are testing.
GCD finds the greatest denominator between 2 integers. The 2 integers you feed in to the GCD function are
the integer you are testing and its square root (rounded down to an integer).
Hint: check out the BigInteger class, there is a method which may help you.
If the GCD of the integer being tested and its root is 1 then the integer being tested is prime.
Sieve: another name for filter.
Essentially you filter out all integers that are known to be prime. Test for i mod Pn != 0 where Pn is a prime number in a list of known or discovered prime numbers. If the mod test == true then don't bother performing a GCD.
Most implementations of Sieve of Erasthonese process 1..100 (as an example) simply skip every even integer as no even integer can be prime.
In your case you need to filter out -ve integers, 0, 1 and any integer that is even. Every other number you test for GCD( i, (int)sqrt(i) ) == 1, if the GCD is 1 in this test you have a prime.
That should just about do your homework for you I think.
>Every other number you test for GCD( i, (int)sqrt(i) ) == 1, if the GCD is 1 in this test you have a prime.Let's try that.i =21GCD ( 21, (int) sqrt(21)) = GCD (21, 4) = 1
Here.
class Sieve {
public static void main(String[] args) {
int[] numbers=new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
boolean[] prime=new boolean[101];
for(int i=0; i<prime.length; i++) prime[i]=true;
int sqrt=(int)Math.sqrt(prime.length-1);
prime[0]=prime[1]=false;
for(int i=2; i><=sqrt; i++) {
if (prime[i])
for(int j=2*i; j<prime.length; j+=i)
prime[j]=false;
}
for(int i=0; i><numbers.length; i++)
if(prime[ numbers[i] ])
System.out.println(numbers[i]+" is prime.");
}
}
>
Of course you can change the array numbers to contain any numbers between 1 and 100 and it will still work.
> >Every other number you test for GCD( i, (int)sqrt(i)
> ) == 1, if the GCD is 1 in this test you have a prime.
>
> Let's try that.
> i =21
> GCD ( 21, (int) sqrt(21)) = GCD (21, 4) = 1
I could kick myself sometimes, you are quite right.
The test for prime is if all of the series of numbers from 1 to sqrt(N) yield a gcd of 1, you skip even values
> The test for prime is if all of the series of numbers from 1 to sqrt(N) yield a gcd of 1, you skip even values
Why GCD if a simple modulo % is sufficient?
A number n is prime if the operation n%x yields a result != 0 where is x is each of the series of numbers from 3 to sqrt(N)
Agreed the GCD is overkill just use the %. Then again seems like we're just talking to each other since the OP hasn't checked back in a while.
