How to rewrite an algorithm into python

Question

I am new to Python and want to create an algorithm that would give an output of a list of prime factors of an input, for example:

Input:   factorise(684)

Output:   2 x 2 x 3 x 3 x 19

Or something along those lines

I would need to define a prime number to begin with so the algorithm knows when it has found a prime factor, so was following a function along these lines:

num = 13
if num > 1:
   for i in range(2, num//2):
      if (num % i) == 0:
      print(num, "is not a prime number")
      break
      else:
         print(num, "is a prime number")
            else:
            print(num, "is not a prime number")

I have based this code on another question, applying it to my code the first issue I have come across is indentation (I'm thinking this is a quick fix) as python reports an error but changing one level has a knock on effect and it's proving tedious to align everything where necessary

Secondly this code is written to produce a written output as opposed to a definition - I was hoping someone could help me adapt the lines beginning 'print' as I was unsure what command to use.

Finally I need to work on bringing this together to create a final algorithm - if there any ideas on how to do this that would be appreciated but if I can form this definition I should have a decent starting point to work with

score 1 · Answer 1 · answered Feb 23 '22 at 15:19

If you need a lot of divisions to determine if a number is a prime, you maybe try an other approach where your algorithm has no idea what a prime is. Simply start with divisor 2 try to divide your number by this. as soon as the number cannot be divided by the divisor any more, increment the divisor and so on until divisor == number.

This way you get a prime factorisation without ever checking a numbe to be prime.

Example:

divisor	remaining number	prime factors so far
2	684
2	342	2
2	171	2 * 2
3	57	2 * 2 * 3
3	19	2 * 2 * 3 * 3
4	19	2 * 2 * 3 * 3
5	19	2 * 2 * 3 * 3
6	19	2 * 2 * 3 * 3
7	19	2 * 2 * 3 * 3
8	19	2 * 2 * 3 * 3
9	19	2 * 2 * 3 * 3
10	19	2 * 2 * 3 * 3
11	19	2 * 2 * 3 * 3
12	19	2 * 2 * 3 * 3
13	19	2 * 2 * 3 * 3
14	19	2 * 2 * 3 * 3
15	19	2 * 2 * 3 * 3
16	19	2 * 2 * 3 * 3
17	19	2 * 2 * 3 * 3
18	19	2 * 2 * 3 * 3
19	1	2 * 2 * 3 * 3 * 19

Output: 2 x 2 x 3 x 3 x 19

P.s. of cause you could stop increasing divisor when it reaches sqrt(remaining_number) but calculating this is quite expensive.

score 0 · Accepted Answer · 2022-02-23T15:03:57.877

0

This will fix your checking if a number is prime

num = 13
isPrime = True
for i in range(2, num//2):
    if (num % i) == 0:
        isPrime = False
        break
if isPrime:
    print(num, "is a prime number")
else:
    print(num, "is not a prime number")

edited Feb 23 '22 at 15:03

answered Feb 23 '22 at 14:58

As an optimisation, you can check up to `int(sqrt(num))` (inclusive), as any number above it will require another divisor that is below it. – nonDucor Feb 23 '22 at 15:11
True. Actually if the OP needs to check for several numbers to be primes, it's better to construct a list of prime numbers using the Sieve or Eratosthenes – Feb 23 '22 at 15:28

score 0 · Answer 3 · answered Feb 23 '22 at 15:17

0

This is a more efficient way of checking if a number is prime.

def isPrime(num):
    for i in range(2,int(num**0.5)+1):
        if(num%i == 0):
            return False
    return True

answered Feb 23 '22 at 15:17

Charlie Ciampa

75
1
9

How to rewrite an algorithm into python

3 Answers3