Computer Science Java Programming Help

[JasonJo]

Computer Science Java Programming Help!

Determine whether or not an integer given by the user is a prime number. You may assume that the number is greater than or equal to 2. You may conditions that are in the form “if x is divisible by y” when writing your algorithm.

HINT: One way of solving this problem is to start with the assumption that the number is going to be prime. If you find at any point in your algorithm that this is not the case you should print a message saying it isn’t and then immediately exit the program (Halt). Otherwise, print a message that the number is prime at the end of your program before exiting.

NOTE: If you choose to use this algorithm for writing your program in Question 2, the Java code “((x % y) == 0)” will be true if and only if x is divisible by y (it literally means that the remainder when x is divided by y is equal to zero). It might also be helpful to know that the line of code “System.exit(0);” can be used to terminate the program at any point you wish.

my problem is:
lets say the number input is 9000203. So my algorithm would be, see if input is divisible by: 1,2,3,4,5,6?

any help on constructing this algorithm? thanks

 

[Nylex]

my problem is:
lets say the number input is 9000203. So my algorithm would be, see if input is divisible by: 1,2,3,4,5,6?

any help on constructing this algorithm? thanks

Well if you're going to do that (which is probably the way I'd do it as well), then where's the problem with your algorithm? All you really need to do is ask yourself what you can say in both cases (ie. whether or not the input is divisible exactly by 1, 2, 3,...).

 

[AKG]

DON'T TEST "1". Every number is divisible by 1, this won't give you any information, and depending on your program, it may give you wrong information. Also, how high do you plan on going up? I'm sure you plan on going past 6, but how high? If N is the input number, you don't have to go all the way up to N. Also, if you've tested if N is divisible by n, and it turns out that it's not, then do you need to test if it's divisible by 2n, 3n, 4n, ...? And of course, if your number is divisible by n, you'll halt. For 19, it suffices to check whether it's divisible by 2 or 3. If not, then that's enough to say it's prime.

 

[neurocomp2003]

go look up prime factorization...the simplest algorithm.

 

[JasonJo]

would this algorithm be valid, I am using psuedo code

Get a value for n
Set divisor to n-1
If n = 2
Then
Print the message "The number"
Print the value of n
Print "is a prime number."
Else
while (divisor >= 2) Do
If (n % divisor)
Then
Print the message "The number"
Print the value of n
Print "is not a prime number."
Else
Set divisor = divisor - 1
End if
End While
End if

Print the message "The number"
Print the value of n
Print "is a prime number."

this is a pretty inefficient algorithm, because if n isn't divisible by 2, it isn't divisible by any multiples of 2.

 

[NateTG]

If you want efficient algoritms you can get some heavy stuff:
http://mathworld.wolfram.com/PrimalityTest.html

That said, you could make things a good bit tighter and cleaner:

for(divisor=int(sqrt(divisor));divisor>1;divisor=divisor-1) {
   break if(n%divisor == 0);
}
if(divisor > 1) {
   print "The number n is not a prime";
} else {
//This would need an extra clause if you had to deal with numbers <=2.
   print "The number n is a prime";
}

Looking at what you've got, it looks like it would print "N is a prime number" for any number, and would spam "N is not a prime number" for numbers that are not prime.

 

[JasonJo]

i am taking an intro to compsci class, and i basically haven't even been introduced to the break lingo or anything like that.

he doesn't mind if its inefficient.

anything you can suggest to change my algo that doesn't involve higher level stuff?

 

[chroot]

The classic algorithm is very simple: test all numbers between 2 and sqrt(N), where N is the input number. If it passes every test (i.e. the remainder is never zero for any divisor), then it's prime.

- Warren

 

[JasonJo]

UNIX Java code

public class prime
{
public static void main (String[] args)
{
int n, divisor;
n = Console.readInt("Please enter a value for n: ");
divisor = n-1;
while (divisor >= 2)
{
if (n % divisor==0 )
{
System.out.println("The number " + n + " is not a prime number.$
System.exit(0);
}
divisor = divisor - 1;
}
System.out.println("The number " + n + " is a prime number.");
}
}

i just compiled it and ran it


thanks for ur help guys! (IT WORKS!)

 

[NateTG]

UNIX Java code

public class prime
{
        public static void main (String[] args)
        {
        int n, divisor;
        n = Console.readInt("Please enter a value for n: ");
        divisor = n-1;
        while (divisor >= 2)
        {
                if (n % divisor==0      )
                {
                System.out.println("The number " + n + " is not a prime number.$
                System.exit(0);
                }
        divisor = divisor - 1;
        }
        System.out.println("The number " + n + " is a prime number.");
        }
}

i just compiled it and ran it


thanks for ur help guys! (IT WORKS!)

Please use the code tags, it makes things so much easier to read.