shishir dwivedi

Greenhorn

Posts: 9

posted 5 years ago

- 1

The best thing to do to figure out what your program is doing is to use TONS of System.out.println(""); statements. Put it all over the place with messages like "in outer loop" or "in inner loop" or "i is now set to " + i messages.

if you do this, you will quickly find something odd about your code...

if you do this, you will quickly find something odd about your code...

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

posted 5 years ago

This is really a new question, so I split it off onto a new thread.

The program isn't giving any output because the only print line you have is at the bottom of your inner loop. Your inner loop starts with factor = 2, then checks factor % 2 == 0, which is true, so you break out of the loop skipping the rest of the loop body and all iterations after factor = 2. That's probably not what you intended it to do. I agree that working out an algorithm on paper first would work better. (Try factoring a smaller number though, like 36.)

The program isn't giving any output because the only print line you have is at the bottom of your inner loop. Your inner loop starts with factor = 2, then checks factor % 2 == 0, which is true, so you break out of the loop skipping the rest of the loop body and all iterations after factor = 2. That's probably not what you intended it to do. I agree that working out an algorithm on paper first would work better. (Try factoring a smaller number though, like 36.)

posted 5 years ago

Others have given you the basics for debugging; so here's a few free pointers for your code:

1. Why did you decide on

It's wrong; and it's

2. ALL prime numbers, except for 2 and 3, conform to the rule that p = 6n±1, where n is is whole number > 0.

How do you think this might help?

3. Look up Euclid's algorithm for finding the greatest common divisor. Those Greeks certainly knew their stuff; even if they didn't know about sanitary toilets or 0.

4. Think about storing previous results. They'll be a help.

HIH

Winston

- 1

shishir dwivedi wrote:I wrote this code to find the Largest prime number...

Others have given you the basics for debugging; so here's a few free pointers for your code:

1. Why did you decide on

`for(i=2;i<number/2;i++)`? More specifically, where did your limit of

`number/2`from?

It's wrong; and it's

*much too large*.

2. ALL prime numbers, except for 2 and 3, conform to the rule that p = 6n±1, where n is is whole number > 0.

How do you think this might help?

3. Look up Euclid's algorithm for finding the greatest common divisor. Those Greeks certainly knew their stuff; even if they didn't know about sanitary toilets or 0.

4. Think about storing previous results. They'll be a help.

HIH

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

posted 5 years ago

This is one of those things that after you think about it seems like it should be obvious. Take any six consecutive integers. Three of them will be even, so they can't be prime (once you get past 2). Two of the six will be divisible by 3, although one of them will be even and has already been eliminated. So of those six, we have just eliminated four.

Now, on the other hand, this seems like a micro-optimization. we go from checking x numbers to checking~~(2/3)x~~ (1/3)x, and from what I remember of my Big-O notation, these are equivalent.

Note: edited to correct factor
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

- 2

Seetharaman Venkatasamy wrote:Winston Gutkowski wrote: p = 6n±1, where n is is whole number > 0.

interesting!

This is one of those things that after you think about it seems like it should be obvious. Take any six consecutive integers. Three of them will be even, so they can't be prime (once you get past 2). Two of the six will be divisible by 3, although one of them will be even and has already been eliminated. So of those six, we have just eliminated four.

Now, on the other hand, this seems like a micro-optimization. we go from checking x numbers to checking

Note: edited to correct factor

Mike Simmons

Ranch Hand

Posts: 3090

14

posted 5 years ago

I'd say you go from checking x to checking (1/3)x. Still equivalent under Big-O, but potentially worth doing - IF you've first solved all other issues with the code.

fred rosenberger wrote:Now, on the other hand, this seems like a micro-optimization. we go from checking x numbers to checking (2/3)x, and from what I remember of my Big-O notation, these are equivalent.

I'd say you go from checking x to checking (1/3)x. Still equivalent under Big-O, but potentially worth doing - IF you've first solved all other issues with the code.

posted 5 years ago

Yes, but since every theory I know of about predicting primes (including a few patterns and plenty of recursive ideas) has yet to be proved conclusive, it would seem that O(n) is about all we can expect. Therefore, to my mind, anything that can "optimize" that O(n) is worth looking at.

Winston

fred rosenberger wrote:Now, on the other hand, this seems like a micro-optimization. we go from checking x numbers to checking (2/3)x, and from what I remember of my Big-O notation, these are equivalent.

Yes, but since every theory I know of about predicting primes (including a few patterns and plenty of recursive ideas) has yet to be proved conclusive, it would seem that O(n) is about all we can expect. Therefore, to my mind, anything that can "optimize" that O(n) is worth looking at.

Winston

Articles by Winston can be found here

posted 5 years ago

Actually, assuming that any algorithm would at least eliminate even numbers, you were right first time.

Winston

fred rosenberger wrote:Mike Simmons wrote:I'd say you go from checking x to checking (1/3)x.

yeah, crud. reduce by 2/3, leave 1/3...got it mixed up in my post. I'll correct.

Actually, assuming that any algorithm would at least eliminate even numbers, you were right first time.

Winston

Articles by Winston can be found here