1
$\begingroup$

i recently got interested in prime numbers and have used some python code to generate an algorithm that contiuously produces prime numbers sequentially. (given 2 and 3 to make the code simpler) There is a separate algorithm that i am working on that formulates the problem as a system of equations. Before i finish the next one i was wondering if there is any point to this???? The system is set up in such a manner that it calculates if n and n-1 have the same prime factors. If so then n must be a prime. It is currently set up to determine the overlap between two timesteps, and the column values multiplied by the header is the maximum number of multiples that can fit below the value n. This can also be assumed to a nonlinear function where every term is offset by a prime amount and has a prime coefficient, regularly outputs primes when the two equations are set to equal and it is true. Because p and p-1 cannot be equal then it is assumed that p is prime and it is added to the equation. I know there are problems around primes but i am unsure if this is at all contributional or if i am just posing a factoring problem differently?? I do not have a background in math so im sorry if i posed the question vaguely or was unable to elaborate on the formula well. Any input is appreciated.

import numpy as np
listofprimes= np.array([2])
number = np.array([3])
i = 1
while i < 1000:
  pastmultiples = (number-1) // listofprimes
  multiples =  number // listofprimes
  #print('checking : ',number)
  if np.array_equal(pastmultiples, multiples, equal_nan=False) :
      listofprimes = np.concatenate((listofprimes,number))
      print('prime : ', number)
  number += 1
  i += 1

Thats all of it. i can be set to any number 1000 is just for convenience. floor division for p and p-1 by smaller primes. If f(n) = f(n-1) then n must be prime. Add n to primes. Loop

$\endgroup$
2
  • $\begingroup$ Look up the Sieve of Erastothenes. $\endgroup$ Jul 7 at 3:39
  • 1
    $\begingroup$ "if n and n-1 have the same prime factors ... then n must be a prime." There is no $n$ such that $n$ and $n-1$ have the same prime factors. E.g., if $n=7$, then the only prime factor of $n$ is $7$, but the prime factors of $n-1$ are $2$ and $3$, not the same as $7$, so if you're really doing what the quote says you're doing, you'll fail to recognize $7$ as a prime. $\endgroup$ Jul 7 at 4:16
0
$\begingroup$

To put your algorithm a bit more formally;

$$N \text{ is prime if } \lfloor\frac{N}{\{C_1, C_2 ... C_{\sim\frac{N}{logN}}\}} \rfloor = \lfloor \frac{N-1}{\{C_1, C_2 ... C_{\sim\frac{N-1}{log(N-1)}}\}} \rfloor \text{ where } C_K \text{ is the $K^{\text{th}}$ prime}$$

(Note I am estimating the length of the sequence of primes beneath $N$ based on the prime counting function)

This will work, based on the intuition that you outlined in your post (that I wont repeat here). However, the issue here is you must store every prime up to the current prime you are calculating in order to get an answer. This isn't so bad here, but as you start getting into useful territory (ie, numbers large enough that we don't know all the primes) it becomes infeasible, as the memory requried (and the time, as you need to iterate over the entire list) is too much. Specifically, you require O($N(\frac{N}{logN})$) space and time to calculate a sequence of primes using this method (where N is the largest prime in the sequence).

It's a nice way of calculating primes without needing to check all smaller numbers, however I think you might have missed the really obvious answer, that you can just simply divide $N$ by all smaller primes and if any have a remainder of 0, $N$ isn't prime:

import numpy as np
listofprimes = np.array([2])
for N in range(3, 1000):
    N = np.array([N])
    if 0 not in N % listofprimes:
        listofprimes = np.concatenate((listofprimes, N))
        print("prime:", N)

This suffers from the same issue as your algorithm but only needs half the comparisons.

If you really want to do this quickly, you'll need to use a probabilistic method such as Miller-Rabin. These can test for composition ridiculously fast. In fact if you use sympy.isprime that's what it uses (not necessarily Miller-Rabin, but some form of a probabilistic test)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.