how to check among big prime numbers for condition

Question

Out of prime numbers less than 201920190 how to find those that dont have digit '7' in their str representation? I need to count the number(count) of such prime numbers that have no '7' in them.

Std sieve implementation is too slow, it just stuck computing..

def SieveOfEratosthenes(num):
    prime = [True for i in range(num+1)]
# boolean array
    p = 2
    while (p * p <= num):
 
        # If prime[p] is not
        # changed, then it is a prime
        if (prime[p] == True):
 
            # Updating all multiples of p
            for i in range(p * p, num+1, p):
                prime[i] = False
        p += 1
 
    # Print all prime numbers
    for p in range(2, num+1):
        if prime[p]:
                  #here added additional check to only print those that have no digit 7
                  if '7' not in str(p):
                     print(p)
 
 
# Driver code
if __name__ == '__main__':
    num = 201920190
    print("Following are the prime numbers smaller"),
    print("than or equal to", num)
    SieveOfEratosthenes(num)

How to do it better?

Does this answer your question? [Fastest way to list all primes below N](https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n) — President James K. Polk, Jul 10 '22 at 21:39
I found the number in ~20 seconds just by tweaking your code a bit. — Kelly Bundy, Jul 10 '22 at 22:26
Ok. But would be good if you could update your code to actually do the job, i.e., count the primes with no 7-digits. — Kelly Bundy, Jul 10 '22 at 22:33
Please make it *count* (and only show the count). Since that's what it's supposed to do, and it will allow checking (with a smaller number it'll be fast enough), and will let the answer focus on the improvement rather than also having to finish the task. — Kelly Bundy, Jul 10 '22 at 23:14

score 2 · Answer 1 · answered Jul 10 '22 at 23:25

2

Perhaps cheating, but if your priority is simply to get a number you could just download a list of all the primes up to 201920190, e.g. from https://primes.utm.edu/lists/small/millions/ (there are about 12 million of them), and then count through that list.

It's not nearly as satisfying as getting your own sieve code to work, but it's pretty efficient!

answered Jul 10 '22 at 23:25

GB supports the mod strike

1,543
1
11
12

3

I love how even that page says "Programs can find them far faster than they can be downloaded" :-) – Kelly Bundy Jul 10 '22 at 23:29
@KellyBundy I suspect that may depend on whether one includes the time taken to write and debug the program ;-) Regrettably, I've reached the point where I weight coding time much more heavily than run-time in gauging "efficiency". But DIY sieving is much more educational. – GB supports the mod strike Jul 11 '22 at 00:59
I suspect my change to their code is less work than downloading the files and writing code to use them :-P – Kelly Bundy Jul 11 '22 at 01:02
@KellyBundy I was going to say something about opening them in MS Word and using Ctrl-F to count instances of "7" but I can't quite bring myself to do it. – GB supports the mod strike Jul 12 '22 at 00:15
Wouldn't that incorrectly double-count 727, for example? – Kelly Bundy Jul 12 '22 at 00:57
@KellyBundy Details, details! – GB supports the mod strike Jul 13 '22 at 01:12

how to check among big prime numbers for condition

1 Answers1