Harold Blake

Greenhorn

Posts: 2

posted 1 year ago

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!

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!

posted 1 year ago

- 1

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.

Edit: Also, break out of your loop when you encounter the first number that divides evenly.

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

Campbell Ritchie

Marshal

Posts: 55698

163

posted 1 year ago

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®.

Never use numbers instead of booleans; that might be necessary in older languages like C but you should always use booleans in Java®.

posted 1 year ago

Well, presumably when your loop fails, you know what number it failed on, so

Give it a try.

Winston

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

posted 1 year ago

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 (

3. (a bit more advanced) In fact, you only need to check

Have a think how you could use that to make your program more efficient.

HIH

Winston

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

posted 1 year ago

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 wrote:

2. If you check whether the number (n) is odd - and greater than 2 -beforeyou enter the loop, you don't have to check for anyevenfactors, because an odd number can't possibly divide exactly by an even number. And ifnisn't odd, then itcan'tbe 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.

Consider Paul's rocket mass heater. |