Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Prime number program  RSS feed

 
Harold Blake
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello!
I am trying to make a prime number program where the user inserts a number and the program tells them whether the number they inserted is a prime number or not. I have finished that part of the program but there's a problem. When the user inserts a number that isn't a prime number the program has to tell them what the number can be divided by and i have no idea how to do that.
Thanks in advance and sorry for my bad English!
 
Carey Brown
Bartender
Posts: 2993
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can you post what you have so far? (Use "Code" tags when posting.)
 
Harold Blake
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
 
Carey Brown
Bartender
Posts: 2993
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
On line 17 you set result to 1. Why not set it to the number it's divisible by?

Edit: Also, break out of your loop when you encounter the first number that divides evenly.
 
Campbell Ritchie
Marshal
Posts: 55698
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

Never use numbers instead of booleans; that might be necessary in older languages like C but you should always use booleans in Java®.
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Harold Blake wrote:When the user inserts a number that isn't a prime number the program has to tell them what the number can be divided by and i have no idea how to do that.

Well, presumably when your loop fails, you know what number it failed on, so that number - let's call it f - must be at least one of the factors. And if you divide n (the number you're checking) by f, you gets its "partner".

Give it a try.

Winston
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Harold Blake wrote:I am trying to make a prime number program...

Some other things for you:

1. Line 13 is inefficient because the value you're checking against is far too high. Have a think what a better one might be.

2. If you check whether the number (n) is odd before you enter the loop, you don't have to check for any even factors, because an odd number can't possibly divide exactly by an even number. And if n isn't odd, then it can't be prime, can it?

3. (a bit more advanced) In fact, you only need to check prime factors - ie, factors which are themselves prime numbers. The reason being that if a number divides by, say 15 (which is not prime), then you already know that it must divide by either 3 or 5, which you've hopefully checked for already.
Have a think how you could use that to make your program more efficient.

HIH

Winston
 
fred rosenberger
lowercase baba
Bartender
Posts: 12542
48
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:
2. If you check whether the number (n) is odd - and greater than 2 - before you enter the loop, you don't have to check for any even factors, because an odd number can't possibly divide exactly by an even number. And if n isn't odd, then it can't be prime, can it?


fixed that for you

Also, (and ignore this if you don't care about squeezing out every drop of efficiency) you don't have to check every odd number either. Once you find 2 and 3 (which are trivial), you can loop over n from 1 to <some upper limit> and only check (6n - 1) and (6n + 1). Why?

6n - 6 and 6n are divisible by 6.
(6n - 5) is the same as 6(n-1) + 1, which would have been checked on an earlier loop
(6n - 4) and 6n - 2 are both guaranteed to be even.
(6n - 3) is divisible by 3

So you can reduce it to only checking 2/3 of the odd numbers. This doesn't do much good when the numbers are small and there are few factors, but as you get into very large values to test, it can save a lot of time.
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
fred rosenberger wrote:fixed that for you

Cheers. Have some beef.

Winston
 
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!