How to use less memory when finding Deletable Primes?

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?

Answer

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.