programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Finding largest prime factor

shishir dwivedi
Greenhorn
Posts: 9
I wrote this code to find the Largest prime number. but it is not giving any output. I declared variable as long. compiler is not throwing any error but it is not also giving any output why ?

Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
use L to define a Long . because, both l and 1 looks similar in some editor.

and I am not sure. what you are trying to do in your program.I do say before directly writing program, take a pen and write an algorithm/logic.

fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
• 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...

Greg Charles
Sheriff
Posts: 3015
12
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.)

Winston Gutkowski
Bartender
Posts: 10575
66
• 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

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

interesting!

fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
• 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 (2/3)x (1/3)x, and from what I remember of my Big-O notation, these are equivalent.

Note: edited to correct factor

Mike Simmons
Ranch Hand
Posts: 3090
14
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.

Winston Gutkowski
Bartender
Posts: 10575
66
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

Seetharaman Venkatasamy
Ranch Hand
Posts: 5575
thanks fred for your detailed explanation

fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
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.

Winston Gutkowski
Bartender
Posts: 10575
66
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

Mike Simmons
Ranch Hand
Posts: 3090
14
Yeah, but I checked the preceding comments before I posted. In context, we were still talking about checking all x elements.