 # dgeiger's solution

## to Prime Factors in the Delphi Pascal Track

Published at Sep 04 2020 · 0 comments
Instructions
Test suite
Solution

Compute the prime factors of a given natural number.

A prime number is only evenly divisible by itself and 1.

Note that 1 is not a prime number.

## Example

What are the prime factors of 60?

• Our first divisor is 2. 2 goes into 60, leaving 30.
• 2 goes into 30, leaving 15.
• 2 doesn't go cleanly into 15. So let's move on to our next divisor, 3.
• 3 goes cleanly into 15, leaving 5.
• 3 does not go cleanly into 5. The next possible factor is 4.
• 4 does not go cleanly into 5. The next possible factor is 5.
• 5 does go cleanly into 5.
• We're left only with 1, so now, we're done.

Our successful divisors in that computation represent the list of prime factors of 60: 2, 2, 3, and 5.

You can check this yourself:

• 2 * 2 * 3 * 5
• = 4 * 15
• = 60
• Success!

## Testing

In order to run the tests for this track, you will need to install DUnitX. Please see the installation instructions for more information.

If Delphi is properly installed, and `*.dpr` file types have been associated with Delphi, then double clicking the supplied `*.dpr` file will start Delphi and load the exercise/project. `control + F9` is the keyboard shortcut to compile the project or pressing `F9` will compile and run the project.

Alternatively you may opt to start Delphi and load your project via. the `File` drop down menu.

### When Questions Come Up

We monitor the Pascal-Delphi support room on gitter.im to help you with any questions that might arise.

### Submitting Exercises

Note that, when trying to submit an exercise, make sure the exercise file you're submitting is in the `exercism/delphi/<exerciseName>` directory.

For example, if you're submitting `ubob.pas` for the Bob exercise, the submit command would be something like `exercism submit <path_to_exercism_dir>/delphi/bob/ubob.pas`.

## Source

The Prime Factors Kata by Uncle Bob http://butunclebob.com/ArticleS.UncleBob.ThePrimeFactorsKata

## Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you may request help from a mentor.

### uPrimeFactorsTests.pas

``````unit uPrimeFactorsTests;

interface
uses
DUnitX.TestFramework;

const
CanonicalVersion = '1.1.0.1';

type
[TestFixture]
TPrimeFactorsTest = class(TObject)
private
procedure CompareArrays(Array1, Array2: TArray<Int64>);
public
[Test]
//    [Ignore('Comment the "[Ignore]" statement to run the test')]
procedure no_factors;

[Test]
[Ignore]
procedure prime_number;

[Test]
[Ignore]
procedure square_of_a_prime;

[Test]
[Ignore]
procedure cube_of_a_prime;

[Test]
[Ignore]
procedure product_of_primes_and_non_primes;

[Test]
[Ignore]
procedure product_of_primes;

[Test]
[Ignore]
procedure factors_include_a_large_prime;
end;

implementation

uses
System.SysUtils, uPrimeFactors;

procedure TPrimeFactorsTest.CompareArrays(Array1, Array2: TArray<Int64>);
var
i: integer;
begin
Assert.AreEqual(Length(Array1), Length(Array2), ' - Array lengths must be equal');
for i := Low(Array1) to High(Array1) do
Assert.AreEqual(Array1[i], Array2[i], format('Expecting element %d to = %d, Actual = %d',
[i, Array1[i], Array2[i]]));
end;

procedure TPrimeFactorsTest.cube_of_a_prime;
begin
CompareArrays([2, 2, 2], TPrimeFactors.factors(8));
end;

procedure TPrimeFactorsTest.factors_include_a_large_prime;
begin
CompareArrays([11, 9539, 894119], TPrimeFactors.factors(93819012551));
end;

procedure TPrimeFactorsTest.no_factors;
begin

CompareArrays([], TPrimeFactors.factors(1));
end;

procedure TPrimeFactorsTest.prime_number;
begin
CompareArrays(, TPrimeFactors.factors(2));
end;

procedure TPrimeFactorsTest.product_of_primes;
begin
CompareArrays([5, 17, 23, 461], TPrimeFactors.factors(901255));
end;

procedure TPrimeFactorsTest.product_of_primes_and_non_primes;
begin
CompareArrays([2, 2, 3], TPrimeFactors.factors(12));
end;

procedure TPrimeFactorsTest.square_of_a_prime;
begin
CompareArrays([3, 3], TPrimeFactors.factors(9));
end;

initialization
TDUnitX.RegisterTestFixture(TPrimeFactorsTest);
end.``````
``````unit uPrimeFactors;

interface

uses
System.Generics.Collections, System.Math;

type
TPrimeFactors = class
private
class var FFactors: TList<Int64>;

class procedure sieve(Number: Int64);

public
class function factors(Number: Int64): TArray<Int64>;

end;

implementation

{ TPrimeFactors }

class function TPrimeFactors.factors(Number: Int64): TArray<Int64>;
var
Index: Integer;
begin
// First, we'll create a list to temporarily store the factors
FFactors := TList<Int64>.Create;

// Use the Sieve of Eratosthenes to factor the number
sieve(Number);

// Set the length of the result array to the number of factors found
SetLength(Result, FFactors.Count);

// Now, we copy the factors into the result array
for Index := 0 to FFactors.Count - 1 do
Result[Index] := FFactors.Items[Index];

// Clean up
FFactors.Destroy;
end;

class procedure TPrimeFactors.sieve(Number: Int64);
var
Factor: Int64;
begin
// The number one isn't prime, so we can leave early
if Number = 1 then
Exit;

// We start at the first prime, 2
Factor := 2;

// We only need to loop until we reach the square root of Number
while Factor <= Trunc(Number * 1.0) do
begin
// Is this factor a prime factor?
if Number mod Factor = 0 then
begin
// Yes, it is, so we add it to the list of factors

// Add now we test the other factor
sieve(Number div Factor);

// Set the factor to be great than the start number to force
// exit of the loop
Factor := Number + 1;
end;

// Lastly, we need to move to the next possible factor
if Factor = 2 then
// The second prime is 3, so we only need to add one to Factor
Inc(Factor)
else
// All remaining primes are odd number, so we add two to Factor
Inc(Factor, 2);
end;
end;

end.``````