If you have an array with repeated numerical data, determine which is the prime that is repeated the most

Question

I would like to see to roadmap to solve this algorithm I was trying:

cd = int(input("Enter the number of elements: "))
A = []
for i in range(cd):
 el = input("")
 A.append(el)

c = 0 
while c < cd:
 cm = 0
 c2 = 1
 while c2 < A[c]:
     if A[c] % c2 == 0:
         cm  = cm + 1  
     c2 += 1
 if cm == 2:
     P1 = A[c]
 c += 1

But then I got stuck. Notice how the style the code is written I would like to see the same style for the solution

restrictions: dictionaries are not allowed

Answer 1

You can use a twist on the sieve of Eratosthenes by placing the count of numbers in the sieve instead of simple True/False flags. Clearing the multiples of each factor out of the sieve will invalidate the counts for non-primes. This will leave the sieve with number counts only on positions that are prime numbers:

A = [13, 70, 33, 83, 76, 41, 4, 38, 70, 56, 38, 65, 95,
     83, 85, 38, 92, 23, 30, 47]

# Setup Sieve of Eratosthenes for largest number
# prime flags contain count of corresponding number
isPrime = []
maxN    = -1
for n in A:
    if n > maxN:
        isPrime += [0] * (n - maxN)
        maxN = n
    isPrime[n] += 1

# perform sieve     
p   = 2
inc = 1 
while p*p <= maxN:
    if isPrime[p] >= 0:     # clear out counts for multiples of primes
        i  = p*p       
        while i <= maxN:
            isPrime[i] = -1
            i += p*inc
    p  += inc
    inc = 2

# find number that is prime and has highest count
prime = None
count = 0
for n in A:
    if isPrime[n] > count:
        prime = n
        count = isPrime[n]

output:

print("most frequent prime:", prime, " found", count, "time(s)")

most frequent prime: 83  found 2 time(s)

Alternatively, you could progressively eliminate the non primes from the list by performing divisor test on remaining elements. With the remaining list of only prime numbers, find the one with the highest count:

# remove non-primes
primes = A
p      = 2
inc    = 1
more   = True
while primes and more:
    more = False
    remaining, primes = primes, []
    for n in remaining:
        if n % p == 0: continue 
        primes.append(n)         
        if p*p <= n:
            more = True
    p  += inc
    inc = 2

# get highest count    
prime   = None
count   = 0
counted = []
for n in primes:
    if n in counted: continue
    counted.append(n)
    c = 0
    for m in primes:
        if m == n:
            c += 1
    if c > count:
        prime, count = n, c

Which method is faster depends on the data (largets number vs number of items, proportion of primes, ...)

Note that I intentionally avoided using python built-in functions (len,range,max,...) and data structures (dictionary, set,...). More efficient constructs could streamline and improve the code depending on what you are allowed to use.