Find the greatest prime number with 7 as the last digit in $\{1,\ldots, n\}$

Question

Let's suppose $n$ is an integer around 250000. Using Java, I need to find the greatest prime number that ends with 7 and belongs to ${1, \dots, n}$. Also, I need to keep an eye on computational complexity and try to lower it as much as I can. So I was thinking of using Sieve of Eratosthenes and looping through an array of boolean values and returning first one from the end that $\mod 10$ returns $7$.

It would keep the whole thing simple I guess, but I was wondering what would the more efficient approach be. Unless, there is a way to easily avoid having an array, but I couldn't think of any. Any ideas for an efficient algorithm?

Answer 1

About $1$ in $\log n$ numbers is prime around $n$. For $n=250000$ that is about $1$ in $13$, so it is much more efficient to just start downward from $n$ and try the primes. You can do simple division tests to eliminate multiples of $3, 7$ and a few other small primes, then use the Fermat primality test. You can look up on the internet the few examples where the Fermat test fails and hardcode them, or you can use one of the tests that guarantees primality. You won't have to look far. This is much more efficient than sieving.

I tried explicitly for $n=250000$ and only had to try four. $249967$ is prime.

Answer 2

Even if you were to just use pure trial division, your computational complexity would only be $N\sqrt N$, (you only need to trial divide by numbers less then $\sqrt A$ to test if $A$ is prime). In this case that gives you an upper bound of about 100 million operations, which is less than a second on most modern computers.

Answer 3

In Mathematica: Find the prime number that is just above 250000:

Assuming[n \[Element] Integers, Solve[Prime[n] > 250000, n]]

yielding $22045$; that is, the 22045th prime number has a value just above 250000. Now start from that prime and go "backwards" (smaller) by how ever many candidate primes you want, and select those whose last digits are $7$:

Select[Prime[Range[22045, 22000, -1]], Mod[#, 10] == 7 &]

(*

{250007, 249967, 249947, 249857, 249827, 249797, 249737, 249727, 249677, 249647, 249607, 249517, 249497}

*)

So clearly $249967$ is the value you seek. This took $0.020087$ seconds on a Mac Pro.

By the way, Mathematica tells you in $0.036767$ seconds how many primes below 250000 end in $7$:

Length[Select[Prime[Range[22045]], Mod[#, 10] == 7 &]]

(*

5518

*)

Furthermore, it took less than $0.3$ seconds to solve the problem for $n = 10^{11}$, which yielded $99999999977$.

In short: if you can, skip Java and coding sieves and hardcoding exceptions and such and use a language powerful enough to have number theoretic functions built in.

Here is some ugly code that is, however, general and quite fast:

greatestPrimeLessThanNEndinginP[n_Integer, p_Integer] := 
 Assuming[z \[Element] Integers,
  (z = Last[q /. Solve[Prime[q] > n, q][[1]]][[2, 2]]);
  Max[Select[
    Prime[Range[Floor[.9 z], z - 1]], Mod[#, 10] == p &]]
  ]

greatestPrimeLessThanNEndinginP[854, 7]

(*

827

*)