Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

liliy Group Title

Write a method that determines whether a given number is prime. Note that you run a loop i/2

  • one year ago
  • one year ago

  • This Question is Closed
  1. srossd Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Well, you could do this a lot of different ways. One way is to check every number under n to see if it divides n. Here's the code for that (in Java first, and then Python, tell me if you want it in a different language): public boolean isPrime(int n) { for(int i = 2; i < n; i++) { if(n % i == 0) return false; } return true; } def isPrime(n): for i in range(2,n): if(n % i == 0): return False return True I'll post an explanation of a more efficient way to do this next.

    • one year ago
  2. srossd Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    A few mathematical observations can vastly improve the running time of this method. The first of those observations is that we don't need to check every number 2 through n-1; we only need to check up to the square root of n. Write out the factors for some composite numbers to convince yourself of that; it's impossible to have factors above sqrt(n) without having some below it too. Here's another observation: think about taking all the values of i in mod 6. Things that are 0, 2, 3, or 4 mod 6 are composite, since they're divisible by either 2 or 3 (the exception to that rule being, of course, 2 and 3 themselves). So, given those two pieces of information, here's java and python code to check primality much much faster than the other code: public boolean isPrime(int n) { if(n % 2 == 0 || n % 3 == 0) return false; int i = 5; while(i <= Math.sqrt(n)) { if(n % i == 0) return false; if(i % 6 == 5) i += 2; else i += 4; } return true; } def isPrime(n): if n % 2 == 0 or n % 3 == 0: return False i = 5 while i < math.sqrt(n): if n % i == 0: return False if i % 6 == 5: i += 2 else: i += 4 return True There you go, tell me if you have more questions.

    • one year ago
  3. liliy Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    but my teacher said use the i/2 method , wat is that?

    • one year ago
  4. slotema Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    One way to use approximately i/2 iterations is by simply excluding all even numbers (except for two), since they are a multiple of two. Therefore, you would only need to check if the number is a multiple of 2 and the odd numbers (3, 5, 7, 9, 11, etc.)

    • one year ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.