News for hackers. Stuff that matters.
Re:Prime number patterns by mrcactu5 on Tuesday November 11, 2014 @01:34PM (#8591362)
the UI is very nice... where did you find 50 million primes? https://github.com/chrisdavies/primepattern/tree/master/sets

I found them: https://primes.utm.edu/lists/small/millions/ He says: Usually it is faster to run a program on your own computer than to download them.

Here in numpy:

  import numpy as np

  N = 1000000

  n = np.arange(N)+2
  p = []

  while(len(n) > np.sqrt(N)):
      p += [n[0]]
      n = n[np.where(n% p[-1] != 0)]

  print len(p), N/np.log(N)
Re:Prime number patterns by thomasahle on Tuesday November 11, 2014 @01:52PM (#8591475)
I like this way of using numpy. This resembles the sieve of eratosthenes, so you'd think it was fast.

However `n%p[-1]` isn't fast to do, your inner loop ends up taking nearly linear time. At least linear in the final number of primes, which is larger than `N/logN`. Hence your algorithm runs in `N^(3/2)` whereas eratosthenes is `NloglogN`.

Funny how many versions of this algorithm there are out there.

Re:Prime number patterns by mrcactu5 on Wednesday November 12, 2014 @08:00AM (#8595226)
I noticed it ran a bit slow... it is supposed to be Eratosthenes Sieve
Re:Prime number patterns by christophilus on Tuesday November 11, 2014 @01:35PM (#8591371)
Hm. I should credit the source... Will put that on my todo list tonight. I transformed these into JSON: https://primes.utm.edu/lists/small/millions/
Re:Prime number patterns by christophilus on Tuesday November 11, 2014 @01:37PM (#8591387)
Yeah. I thought about shrinking the dataset down to 10k primes instead of 1m primes, as the patterns would still hold up, but the load/rendering times would greatly improve.
Re:Prime number patterns by mrcactu5 on Wednesday November 12, 2014 @08:03AM (#8595235)
I appreciate having such a ridiculous number or primes. For certain cryptography problems I need primes around 10^15 or even bigger.