Need help with a problem - Page 2

Bench · #11 (**permalink**) 07-23-2007, 12:53 PM

Given any positive integer, N,

First of all, deal with your special cases, 0 and 1.

Then test each number from 2 upto the square root of N (Which you can truncate to an int) to see if its a potential divisor.

if any of these numbers are evenly divisble, then N is not prime. Otherwise, N is prime

Try to work out the steps on paper in pseudocode before creating the program if you're not sure.

rpgfan3233 · #12 (**permalink**) 07-24-2007, 12:45 AM

I agree. No problem is terribly difficult once you figure out some of the most important steps properly.

Pseudocode is a great tool that I use somewhat often. I highly recommend it if you have trouble figuring out the right bit of code to do what you want.

I'd also like to recommend making 2 a special case as well, since it is the only prime number that is also even. From there, you can test every odd number (3, 5, 7, 9, etc.) up to the square root of N, as Bench mentioned. It saves a lot of time to test only the odd numbers and it saves even more time when you test only up to the square root of N. However, if you don't know how to use the square root or don't want to, just N/2 will do as long as you aren't working with a large number N.

I hope we helped you a bit more. Good luck with your code!

hnkplaya · #13 (**permalink**) 07-25-2007, 10:11 AM

yes but it is suppose to composite the largest divisible number of the value typed in. I dont know that is why I asked because I was not sure what I was doing there

rpgfan3233 · #14 (**permalink**) 07-25-2007, 12:08 PM

Below is some pseudocode that I created. All it does is find the greatest divisor (e.g. for the number 93, the biggest integer that can evenly be divided is 31). After finding it, it outputs the original number, followed by prime or composite. If it is composite, the greatest divisor is also outputted. Note that 2 is specially treated as it is an exception to the statement "all even numbers are not prime". The details of the code:

Create and initialize variables
User inputs value and value is stored in both number and number_backup
If number is greater than 2 (0 and 1 are neither prime nor composite), then the following happens:
* Test for division by odd values via loop_variable as the odd value. If divisible, the value of loop_variable is stored in greatest_divisor.
* Test for division by 2 repeatedly until number is no longer even, in which case it is no longer evenly divisible by 2. During the test, greatest_divisor is multiplied by 2 and number is divided by 2.
* Once the test is finished, it has multiplied too many times, so it must be divided by 2.
Now greatest_divisor holds the value of the largest integer that can evenly divide the original number entered.
The original number entered is then outputted to the screen and a test begins:
* If the original number entered is less than 2, it cannot be prime and it also cannot be composite.
* If the greatest_divisor is only 1, that means that it could not evenly be divided by something other than itself, meaning it is prime. If the original number entered was 2, then that is also prime.
* If the above conditions are not satisfied (greatest_divisor is not equal to 1 and the original number is not 2), then the number is composite.
The appropriate rest of code is outputted and then the program ends.

Here is the code:

Code:

Create greatest_divisor As Integer
Create number As Integer
Create number_backup As Integer
Create loop_variable As Integer
number = 2
number_backup = 2
greatest_divisor = 1
loop_variable = 3

Print "Enter a positive integer: "
Input number

number_backup = number

Comment
    I'm assuming division with integers actually
    does integer division like it does in C
    (it is meant to be C code after all...)
End Comment
While loop_variable <= (number / 2)
    Comment '%' is the remainder operator (the Mod operator in this case)
    If (number % loop_variable) = 0 Then
        greatest_divisor = loop_variable
    End If
    loop_variable = (loop_variable + 2)
End While

Comment We still need to test multiples of 2 such as 2, 4, 8, etc.
If (number % 2) != 1 Then
    While (number % 2) != 1
        greatest_divisor = (greatest_divisor * 2)
        number = (number / 2)
    End While
    greatest_divisor = (greatest_divisor / 2)
End If

Print number_backup
Comment
    2 is a special case, just like a number such as 1
End Comment
If number_backup < 2 Then
    Print " NOT PRIME AND NOT COMPOSITE\n"
Else If (greatest_divisor == 1) Or (number_backup == 2) Then
    Print " PRIME\n"
Else
    Print " COMPOSITE ", greatest_divisor, "\n"
End If

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

The Following 2 Users Say Thank You to Bench For This Useful Post:
rpgfan3233 (07-24-2007), TeraTask (07-25-2007)

The Following User Says Thank You to rpgfan3233 For This Useful Post:
TeraTask (07-25-2007)