A community for students. Sign up today!
Here's the question you clicked on:
 0 viewing
 2 years ago
Write a method that determines whether a given number is prime. Note that you run a loop i/2
 2 years ago
Write a method that determines whether a given number is prime. Note that you run a loop i/2

This Question is Closed

srossd
 2 years ago
Best ResponseYou've already chosen the best response.0Well, 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.

srossd
 2 years ago
Best ResponseYou've already chosen the best response.0A 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 n1; 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.

liliy
 2 years ago
Best ResponseYou've already chosen the best response.0but my teacher said use the i/2 method , wat is that?

slotema
 2 years ago
Best ResponseYou've already chosen the best response.0One 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.)
Ask your own question
Ask a QuestionFind more explanations on OpenStudy
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
 Engagement 19 Mad Hatter
 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.