• Post Reply Bookmark Topic Watch Topic
  • New Topic

Finding largest prime factor  RSS feed

 
shishir dwivedi
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Java Windows XP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Chrome Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Firefox Browser IntelliJ IDE Java Mac Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Java Windows XP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote: p = 6n±1, where n is is whole number > 0.

interesting!
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Java Windows XP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
thanks fred for your detailed explanation
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yeah, but I checked the preceding comments before I posted. In context, we were still talking about checking all x elements.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!