1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Computer Science Java Programming Help

  1. Jun 10, 2005 #1
    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
     
  2. jcsd
  3. Jun 10, 2005 #2
    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,...).
     
  4. Jun 10, 2005 #3

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  5. Jun 10, 2005 #4
    go look up prime factorization...teh simplest algorithm.
     
  6. Jun 10, 2005 #5
    would this algorithm be valid, im 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 isnt divisible by 2, it isnt divisible by any multiples of 2.
     
    Last edited: Jun 10, 2005
  7. Jun 10, 2005 #6

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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:

    Code (Text):

    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 woudl spam "N is not a prime number" for numbers that are not prime.
     
  8. Jun 10, 2005 #7
    i am taking an intro to compsci class, and i basically havent even been introduced to the break lingo or anything like that.

    he doesnt mind if its inefficient.

    anything you can suggest to change my algo that doesnt involve higher level stuff?
     
  9. Jun 10, 2005 #8

    chroot

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
     
  10. Jun 10, 2005 #9
    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!!)
     
  11. Jun 10, 2005 #10

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    Please use the code tags, it makes things so much easier to read.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Computer Science Java Programming Help
  1. Java help (Replies: 1)

  2. Computer Science (Replies: 4)

Loading...