How to use less memory when finding Deletable Primes?

Question

Edit:

1.there was some confusion on the memory limit. I only have 1MB of memory to work with and there is no time limit.

2.the entry number n specifies the n digits number that is supposed to be checked. if you enter 3 it will check numbers from 100-999 to see if they are Deletable primes or not

3.it was addressed that division trial for prime numbers takes a long time to process. what algorithm is less memory consuming

4.im using python 3.9

5.i don't measure memory usage. there is an auto-assessment that checks memory usage

6.maximum of n is 8

Question:

I have the assignment to write a script that gets a number n as input and goes through all n digit numbers and does the following:

If the number i is a prime number, cut the right digit and test if it's a prime number again and repeat this until the last digit. If all numbers generated from i are prime numbers, return i (for example 797 fits in the description, 797, 79, 7).

Writing the code isn't the problem, there is a memory limit that my script doesn't fulfill.

Here's the code:

import math

def prime(n):
    if n == 1:
        return 0
    for i in range(2, int(math.sqrt(n) + 1)):
        if n % i == 0:
            return 0
    return 1

n = int(input())
   
def veryprime(i, n):
    p = 0
    for j in range(n-1, -1, -1):
        if j == 0:
            if prime(i) == 0:
                p = 1
                break
                del j
        else:
            if prime(i // (10**j)) == 0:
                p=1
                break
                del j
                
    if p == 0:
        print(i)

for i in range(10**(n-1), 10**n):
    veryprime(i, n)

What can I do to use less memory?

looking at the code nothing look like it use to much memory, unless you're using python 2, in which case change range for xrange, the trial division test can also be improved to make it a bit faster — Copperfield, Dec 14 '20 at 20:57
Does this answer your question? [Python Finding Prime Factors](https://stackoverflow.com/questions/15347174/python-finding-prime-factors) — Joe Ferndz, Dec 14 '20 at 21:00
There are so many answers on StackOverflow to address your question. Here's one more. Please use SO to see if you can get the answers before you create new questions. https://stackoverflow.com/questions/453793/which-is-the-fastest-algorithm-to-find-prime-numbers — Joe Ferndz, Dec 14 '20 at 21:04
@JoeFerndz the OP don't want to factor the number, but to check if its a deletable prime — Copperfield, Dec 14 '20 at 21:08
Realistically this seems more of an issue that Python isn't particularly fast. If Python isn't a requirement, try a lower level language eg Java, C++, C etc — dwb, Dec 14 '20 at 21:14
@dantechguy No, the algorithm is just bad. I'm sure this can be done in Python with decent speed. (Or equally slow in C++) — mkrieger1, Dec 14 '20 at 21:16
@dantechguy a trial division test for prime will be slow regardless of language you do it... — Copperfield, Dec 14 '20 at 21:18
looking definitions, this is more specific case of deletable prime, a [truncatable prime](https://mathworld.wolfram.com/TruncatablePrime.html) — Copperfield, Dec 14 '20 at 21:37
Concerning 3., presumably *no* algorithm is less memory-consuming than trial division. Typically, algorithms are faster by using *more memory* in clever ways (for example by remembering previous intermediate results to avoid recalculating them). — mkrieger1, Dec 14 '20 at 22:21
Nothing in this code uses anything like a large amount of memory (unless you are inputting a truly enormous value of `n`). Even `10**1000000` only uses about 400Kb of memory. — chepner, Dec 14 '20 at 22:22
@mkrieger1 Yeah, I just computed all deletable primes in Python using trial division, took 0.01 seconds total. — Kelly Bundy, Dec 14 '20 at 23:02
Is this problem available online somewhere? If so, what's the link? — Kelly Bundy, Dec 14 '20 at 23:10

Kelly Bundy · Accepted Answer · 2020-12-15T00:14:46.510

Here's a way to compute all of them in about 0.01 seconds and with little memory (adjust to your n-digits usage as needed). Instead of starting with long numbers and removing digits, start short and append digits.

from math import isqrt

def isprime(n):
    return n > 1 and all(map(n.__mod__, range(2, isqrt(n) + 1)))

P = [0]
while P:
    P = [q for p in P for d in range(10) if isprime(q := p * 10 + d)]
    print(P)

Output:

[2, 3, 5, 7]
[23, 29, 31, 37, 53, 59, 71, 73, 79]
[233, 239, 293, 311, 313, 317, 373, 379, 593, 599, 719, 733, 739, 797]
[2333, 2339, 2393, 2399, 2939, 3119, 3137, 3733, 3739, 3793, 3797, 5939, 7193, 7331, 7333, 7393]
[23333, 23339, 23399, 23993, 29399, 31193, 31379, 37337, 37339, 37397, 59393, 59399, 71933, 73331, 73939]
[233993, 239933, 293999, 373379, 373393, 593933, 593993, 719333, 739391, 739393, 739397, 739399]
[2339933, 2399333, 2939999, 3733799, 5939333, 7393913, 7393931, 7393933]
[23399339, 29399999, 37337999, 59393339, 73939133]
[]

Though like others have said, your code doesn't use much memory, either. My guess is that the assessment system doesn't measure properly. Like, measuring not just the memory used by your solution but also including the general Python overhead and the assessment system's overhead. Similar to for example LeetCode. There's a problem where the input is an integer 1 <= n <= 200 that can be solved with return n - 1, and LeetCode reports "Memory Usage: 14 MB" for that.

This definitely uses less memory than my code but its still exceeds the memory limit. there is probably something wrong with auto-assessment so I'm closing down this thread. — Anthraxff, Dec 14 '20 at 23:38
@Anthraxff I think it uses a little *more* memory than yours, for the lists. Both take very little, though, I'd say at most a few kilobytes. And most of that for importing `math` (which we could replace by computing the square root as `int(n ** .5)` instead). — Kelly Bundy, Dec 14 '20 at 23:42
@Anthraxff Just to be sure: You said *you* are using Python 3.9. Is the assessment system also using 3.9? — Kelly Bundy, Dec 14 '20 at 23:46

Alain T. · Answer 2 · 2022-08-17T13:25:38.877

I would suggest a recursive generator to further reduce the memory footprint. Also, the ending digits of prime numbers can only be 1, 3, 7 or 9 so you can limit the extensions to those digits. Since the numbers will eventually be cut down to their first digit, the first digits can only be 2, 3, 5 or 7 which also reduces the number of candidates.

def isPrime(N):
    return N==2 or N%2 and all(N%f for f in range(3,int(N**0.5)+1,2))


def delPrimes(N):
    if N == 1:
        yield from (2,3,5,7) # first digits
    else:
        yield from (p*10+d for p in delPrimes(N-1) for d in (1,3,7,9)
                    if isPrime(p*10+d)) # last digits

output:

for dp in delPrimes(3): print(dp)

233
239
293
311
313
317
373
379
593
599
719
733
739
797


for dp in delPrimes(8): print(dp)

23399339
29399999
37337999
59393339
73939133

timeit(lambda : all(delPrimes(8)),number=1)

0.003959891999997467 second

score -1 · Answer 3 · edited Dec 15 '20 at 11:37

-1

Think recursive !

import math

def prime(n):
    if n == 1:return False
    for i in range(2, int(math.sqrt(n)+1)):
        if n % i == 0:return False
    return True

def very_prime(n,liste):
    if prime(n):
        if n<10:return liste+[n]
        else:return very_prime(n//10,liste+[n])
    else:return liste

print(very_prime(499391,[]))

n is very prime when the output list has length the numbers of digit in n aka math.floor(math.log10(n))+1.

edited Dec 15 '20 at 11:37

E_net4

27,810
13
101
139

answered Dec 14 '20 at 22:40

smed

148
1
10

why recursion?? – Copperfield Dec 14 '20 at 22:45
To me it's a clear use case. Take 499391 as an entry : `prime(499391) : True` `prime(49939) : True` `prime(4993) : True` `prime(499) : True` `prime(49) : False` Hey, c'mon, won't you tell me it does have a recursive flavour !? – smed Dec 14 '20 at 22:56
two thing: function call use memory, by making your program recursive your use even more memory than really necessary and second you keep track of the number chain in a list, which again use memory, and you even go and make even more list with `+` which waste even more memory and there is no need to remember the whole path, as soon as any point in the path fail, the test fail... all that can be done iterative and the OP want to minimize memory usage... – Copperfield Dec 14 '20 at 22:58
You are right. Recursion comes first at mind, at least when you come from mathematics... Then linear programming could help optimizing things ? At leats memoization ? – smed Dec 14 '20 at 23:02
in this case there is no need to memorize anything, and the OP said time is no concern so optimization that use memory are unwelcome in this case – Copperfield Dec 14 '20 at 23:06

How to use less memory when finding Deletable Primes?

3 Answers3