search

andrew-field / projecteuler-go

Testing and practising Go with Project Euler
MIT License
0 stars 0 forks source link

Challenge 3: Largest Prime Factor #6

Closed andrew-field closed 6 years ago

andrew-field commented 6 years ago

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

What is the largest prime factor of the number 600851475143?

andrew-field commented 6 years ago

For this I challenge I wanted to make it more general. This program will find the largest prime factor of any number. I created a new library called number theory to house my factorisation logic. As of the time of writing, one program to generate prime numbers below a certain max size, one program to continuously generate prime numbers and one program to provide a prime factorisation of any number. The use provides the challenge number at runtime. The program simply returns the largest number returned to it from the number theory library.

andrew-field commented 6 years ago

primeNumbersBelowCeiling: This program creates a slice of all the numbers from 2 to the max prime size 'ceiling'. It uses a Euclidean sieve/Sieve of Eratosthenes to then find all the primes in the slice.

andrew-field commented 6 years ago

primeNumbersContinuously: This uses again an Euclidean sieve/Sieve of Eratosthenes but in parts. The program takes one small slice, the size of which is defined by the user and finds all the primes in that slice before moving on to a new slice. For each new slice it must check all the new numbers against the current prime numbers before sieving.

andrew-field commented 6 years ago

primeFactorisation: This program provides a prime factorisation of a number given at runtime. It simply checks whether each prime number in order is a factor and if so, how many times, before moving on to the next prime.

andrew-field commented 5 years ago

Changed slightly due to the refactor of the library class.

andrew-field commented 3 years ago

Complete refactor. Simply loops through the prime factors to find the largest.