Skip to content

Problem 3: Largest prime factor

Link to the problem: https://projecteuler.net/problem=3.

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

A simple solution

Here we basically try every \(k = 2,3,4,5,...\) and if it is a factor of \(n\), we divide \(n\) by \(k\) as many times as necessary until \(k\) is no longer a multiple. Then we moved to the next \(k\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(defwire main-wire
  600851475143 >= .n
  2 >= .k
  1 >= .lastFactor

  (Repeat
   (-> (When
        (-> .n (Math.Mod .k) (Is 0))
        (-> .k > .lastFactor
            (Repeat
             (-> .n (Math.Divide .k) > .n)
             :Forever true
             :Until (-> .n (Math.Mod .k) (IsNot 0)))))
       (Math.Inc .k))
   :Forever true
   :Until (-> .n (IsLessEqual 1)))

  .lastFactor (Assert.Is 6857 true)
  (Log "Answer"))

(defmesh root)
(schedule root main-wire)
(run root)

[info] [2023-02-24 14:01:39.512] [T-6192] [logging.cpp::62] [main-wire] Answer: 6857

A slightly better solution

\(2\) is the only even prime, so if we check \(2\) separately first, we can increase \(k\) each step by \(2\), avoiding unnecessary checks that would always fail for all even factors.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
(defwire main-wire
  600851475143 >= .n
  1 >= .lastFactor

  (When
   (-> .n (Math.Mod 2) (Is 0))
   (-> 2 > .lastFactor
       (Repeat
        (-> .n (Math.Divide 2) > .n)
        :Forever true
        :Until (-> .n (Math.Mod 2) (IsNot 0)))))

  3 >= .k
  (Repeat
   (-> (When
        (-> .n (Math.Mod .k) (Is 0))
        (-> .k > .lastFactor
            (Repeat
             (-> .n (Math.Divide .k) > .n)
             :Forever true
             :Until (-> .n (Math.Mod .k) (IsNot 0)))))
       .k (Math.Add 2) > .k)
   :Forever true
   :Until (-> .n (IsLessEqual 1)))

  .lastFactor (Assert.Is 6857 true)
  (Log "Answer"))

(defmesh root)
(schedule root main-wire)
(run root)

[info] [2023-02-24 14:01:39.593] [T-5716] [logging.cpp::62] [main-wire] Answer: 6857

A much better solution

Suppose now that the number to test is much larger (e.g. \(4287721622247962\)) and with a big prime as a factor. It could take quite a while to reach that big prime.

This can be simplified with the realisation that at most one prime factor can be greater than \(\sqrt{n}\). In other words, after finding one factor for the remaining number \(n\) we can use \(\sqrt{n}\) as the upper limit for \(k\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
(defwire main-wire
  4287721622247962 >= .n (Log "n")
  .n (ToFloat) (Math.Sqrt) >= .maxFactor
  1 >= .lastFactor

  (When
   (-> .n (Math.Mod 2) (Is 0))
   (-> 2 > .lastFactor
       (Repeat
        (-> .n (Math.Divide 2) > .n)
        :Forever true
        :Until (-> .n (Math.Mod 2) (IsNot 0)))))

  3 >= .k
  (Repeat
   (-> (When
        (-> .n (Math.Mod .k) (Is 0))
        (-> .k > .lastFactor
            (Repeat
             (-> .n (Math.Divide .k) > .n)
             :Forever true
             :Until (-> .n (Math.Mod .k) (IsNot 0)))
            .n (ToFloat) (Math.Sqrt) > .maxFactor))
       .k (Math.Add 2) > .k)
   :Forever true
   :Until (-> .n (IsLessEqual 1) (Or) .k (ToFloat) (IsMore .maxFactor)))

  (If (-> .n (Is 1))
      :Then (-> .lastFactor)
      :Else (-> .n))
  (Assert.Is 5829843479 true)
  (Log "Answer"))

(defmesh root)
(schedule root main-wire)
(run root)

[info] [2023-02-24 14:01:39.672] [T-6312] [logging.cpp::62] [main-wire] n: 4287721622247962
[info] [2023-02-24 14:01:39.730] [T-6312] [logging.cpp::62] [main-wire] Answer: 5829843479

More details on the Project Euler's website: https://projecteuler.net/overview=003.