Waste less time on Facebook — follow Brilliant.
×

Promotion of a very excellent website

Recently, Cody Johnson created NoBash.com, which is a site dedicated to telling you if you are correct in wanting to give on the problem you are working on and start bashing numbers. Since this arose out of a conversation we were having about a name to give to a math web site, I thought it would be fitting to promote his site.

Ironically, of course. Because I have created a very bashy way to test for primality! See if you can come up with a bashier (slower) primality test than this.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
import time
start=time.time()

factors=0

for i in range (1,n+1):
    for j in range (1,i+1):
        if i%j==0:
            factors=factors+1
    if factors==2:
        print i, "is prime."
    if factors!=2:
        print i, "is not prime."

    factors=0

end=time.time()
print "This operation took", end-start, "seconds."

Note by Trevor B.
3 years, 1 month ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

First, create a code that prime factorizes a number. Then, add the number \(2\) to your prime array.

Now every step, you take all the primes in your prime array, multiply them, then add one. Then you prime factorize, and if there are any primes in your prime factorization (which there will be) that are not in the array, add them to the array. Repeat. Guaranteed non-efficiency.

I'm not sure that gives all the prime numbers though. Daniel Liu · 3 years, 1 month ago

Log in to reply

Divide the number by six and check the remainder.exception(2,3). Aamir Faisal Ansari · 3 years, 1 month ago

Log in to reply

@Aamir Faisal Ansari Remainder has to 1 or 5 for a number to prime. Aamir Faisal Ansari · 3 years, 1 month ago

Log in to reply

@Aamir Faisal Ansari \(p\equiv \pm 1\pmod 6\) (\(p\in\mathbb P\), \(p>3\)) is a necessary condition, but not sufficient (e.g., try \(25\)). Mathh Mathh · 3 years, 1 month ago

Log in to reply

@Mathh Mathh Right. Aamir Faisal Ansari · 3 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...