Got Homework?
Connect with other students for help. It's a free community.
Here's the question you clicked on:
 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
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

srossd Group TitleBest ResponseYou've already chosen the best response.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

srossd Group TitleBest ResponseYou've already chosen the best response.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 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.
 one year ago

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

slotema Group TitleBest ResponseYou've already chosen the best response.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
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
 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.