### Author Topic: Variables related question.  (Read 1586 times)

#### RubenMG

• New member
• Posts: 5
##### Variables related question.
« on: February 12, 2018, 05:31:00 pm »
Hi guys! Hope you're all doing well

I have a question, i was trying to do the 3rd Euler project problem. Here i put you the code.

Problem: https://projecteuler.net/problem=3

Code: Pascal  [Select]
1. program Euler_Project3;
2.
3. {The prime factors of 13195 are 5, 7, 13 and 29.
4.
5. What is the largest prime factor of the number 600851475143 ?}
6.
7. var
8.
9.   x : Integer;
10.   i : Integer;
11.   z: Integer;
12.
13.
14. begin
15.
16. i:=13195;
17. z:=0;
18.
19. for x:=1 to 100 do
20.
21.   begin
22.        if i mod x = 0 then
23.        writeLn(x);
24.   end;
25.
26.
28.
29. end.

I was trying first to have the prime factor of the number 13195, the problem is i don't know how to tell the code this:

- Once you have the numbers that are TRUE for the if, then add those numbers into a new variable and multiply them, something like:

Code: Pascal  [Select]
1.
2. if i mod x = 0 then
3.        begin
4.          repeat
5.            z:=x * x;
6.          until z:=13195;
7.        end;
8.
9.

Thank you very much!

Best regards,  Rubén.

#### Blaazen

• Hero Member
• Posts: 2754
• POKE 54296,15
##### Re: Variables related question.
« Reply #1 on: February 12, 2018, 06:46:29 pm »
Input is 13195 and output of your program should be 29*455 ?
Lazarus 2.1.0 r59757M FPC 3.3.1 r40507 x86_64-linux-qt Chakra, Qt 4.8.7/5.11.2, Plasma 5.14.2
Lazarus 1.8.2 r57369 FPC 3.0.4 i386-win32-win32/win64 Wine 3.21

Try Eye-Candy Controls: https://sourceforge.net/projects/eccontrols/files/

#### RubenMG

• New member
• Posts: 5
##### Re: Variables related question.
« Reply #2 on: February 12, 2018, 06:47:58 pm »
Hi!

It should be: 5, 7, 13 and 29.

Bye!

#### Bart

• Hero Member
• Posts: 3311
##### Re: Variables related question.
« Reply #3 on: February 12, 2018, 06:59:10 pm »
First try to get the algorithm right.
You only want to divide by prime numbers.
E.g. prime factors of 60 are 2,3 and 5.
But you also need to know to what power a given prime needs to be raised: 60 = 2^2 * 3 * 5

Prime factorization is not easy, it's computationally intens, that's why it's used in cryptography.

You can use the Seive of Eratosthenes to gather prime numbers.
Note that for N the larges prime factor will always be <= square root of N.

So, for 600851475143 the largest prime factor will be <=775146
And for 13195, it will be <= 114.

For relative small numers (up to 10968163441) you can use my unit that contains a list of the first 10000 primes as a starting point.

Bart

#### RubenMG

• New member
• Posts: 5
##### Re: Variables related question.
« Reply #4 on: February 12, 2018, 07:36:20 pm »
First try to get the algorithm right.
You only want to divide by prime numbers.
E.g. prime factors of 60 are 2,3 and 5.
But you also need to know to what power a given prime needs to be raised: 60 = 2^2 * 3 * 5

Prime factorization is not easy, it's computationally intens, that's why it's used in cryptography.

You can use the Seive of Eratosthenes to gather prime numbers.
Note that for N the larges prime factor will always be <= square root of N.

So, for 600851475143 the largest prime factor will be <=775146
And for 13195, it will be <= 114.

For relative small numers (up to 10968163441) you can use my unit that contains a list of the first 10000 primes as a starting point.

Bart

But regarding one question i asked, how do you save the value of a variable in order to do this:

Code: Pascal  [Select]
1. if i mod x = 0 then
2.        begin
3.          repeat
4.            z:=x * x;
5.          until z:=13195;
6.        end;

Z being z:=5*7*13*29;

Hope it's clear to understand.

Thank you veyr much.

#### howardpc

• Hero Member
• Posts: 2879
##### Re: Variables related question.
« Reply #5 on: February 12, 2018, 08:38:10 pm »
Commonly used containers for storing simple data types (such as your variable z) are arrays or lists.

There are always several ways to approach problems such as this. Here is one solution for you.
Note that the question posed chooses a number large enough (600851475143) to lie outside the range of a longint, so the following cannot be used for it without adaptation.

Code: Pascal  [Select]
1. program Euler_Project3;
2.
3. {\$Mode objfpc}{\$H+}
4.
5. {The prime factors of 13195 are 5, 7, 13 and 29.
6.
7. What is the largest prime factor of the number 600851475143 ?}
8.
9. uses Types;
10.
11.   function GetPrimesBelow(anInt: Integer): TIntegerDynArray;
12.   var
13.     halfRange, i, num: Integer;
14.
15.     procedure Delete(j: Integer);
16.     var
17.       k: Integer;
18.     begin
19.       for k := j to High(Result)-1 do
20.         Result[k] := Result[k+1];
21.       SetLength(Result, Length(Result)-1);
22.     end;
23.
24.   begin
25.     halfRange:=anInt div 2;
26.     case Odd(anInt) of
27.       False: SetLength(Result, halfRange);
28.       True:  SetLength(Result, halfRange+1);
29.     end;
30.     i := 0;
31.     for num := 2 to anInt do
32.       if Odd(num) or (num = 2) then begin
33.         Result[i] := num;
34.         Inc(i);
35.       end;
36.
37.     for num := halfRange downto 3 do
38.       begin
39.         if not (Odd(num) or (num = 2)) then
40.           Continue;
41.         for i := High(Result) downto Low(Result) do
42.           if ((Result[i] mod num) = 0) and (Result[i] <> num) then
43.             Delete(i);
44.       end;
45.   end;
46.
47. var
48.   a, aSqrt, x, product: Integer;
49.   primeArray, primeFactors: TIntegerDynArray;
50.
51.   function IsPrime(anInt: Integer): Boolean;
52.   var
53.     i: Integer;
54.   begin
55.     for i in primeArray do
56.       if i = anInt then
57.         Exit(True);
58.     Result := False;
59.   end;
60.
61. begin
62.   a := 13195;
63.   aSqrt := trunc(sqrt(a));
64.
65.   primeArray := GetPrimesBelow(aSqrt + 1);
66.   SetLength(primeFactors, 0);
67.   for x := 2 to aSqrt do
68.     if IsPrime(x) and ((a mod x) = 0) then begin
69.       SetLength(primeFactors, Length(primeFactors) + 1);
70.       primeFactors[High(primeFactors)] := x;
71.     end;
72.
73.   WriteLn('The prime factors of ',a,' are: ');
74.   for x in primeFactors do
75.     Write(x, ' ');
76.   WriteLn;
77.
78.   product:=1;
79.   for x in primeFactors do
80.     product := product * x;
81.   WriteLn('The product of the prime factors of ', a,' is ', product);
82.
84. end.

#### Bart

• Hero Member
• Posts: 3311
##### Re: Variables related question.
« Reply #6 on: February 12, 2018, 10:22:10 pm »
As I understood the original question, the product was supposed to give the original number back, not just the product of of the primes, but I may be wrong.

Code: [Select]
`The prime factors of 60 are:2 3 5The product of the prime factors of 60 is 30`
Bart

#### Kays

• Full Member
• Posts: 141
• Whasup!?
##### Re: Variables related question.
« Reply #7 on: February 13, 2018, 06:59:18 pm »
[…]
There are always several ways to approach problems such as this. Here is one solution for you.
[…]

I'm tempted to just post the solution, too, but ProjectEuler was meant as challenges.

As I understood the original question, the product was supposed to give the original number back, not just the product of of the primes, but I may be wrong. […]
I think so, too.

I looked back into my study folder. Prime factorization itself was a programming assignment back then in CS1 (general CS class in first semester). The general idea was described in the problem set sheet, though. I translated (and slightly modified) what I'd programmed in java at that time:
Code: Pascal  [Select]
1. program primeFactorization(input, output, stderr);
2.
3. uses
4.         // for intToStr()
5.         sysUtils;
6.
7. function intPrimeFactorization(const n: qword): string;
8.         // nested routine, for less memory allocation and more overview
9.         function ipf(): string;
10.         var
11.                 p: qword;
12.                 s: string;
13.         begin
14.                 p := 2;
15.                 s := emptyStr;
16.
17.                 // test, while we haven't found a prime
18.                 while sqr(p) <= n do
19.                 begin
20.                         // fitting divisor found?
21.                         if n mod p = 0 then
22.                         begin
23.                                 // recursion
24.                                 s := concat(intToStr(p), ' * ', intPrimeFactorization(n div p));
25.                                 // catch next iteration
26.                                 p := n;
27.                         end
28.                         else
29.                         begin
30.                                 inc(p);
31.                                 // have we tested all reasonable integers?
32.                                 if sqr(p) > n then
33.                                 begin
34.                                         // so n is probably a prime
35.                                         s := concat(s, intToStr(n));
36.                                         // catch next iteration
37.                                         p := n;
38.                                 end;
39.                         end;
40.                 end;
41.
42.                 ipf := s;
43.         end;
44. begin
45.         // base case: …, 2, 3 are already prime
46.         if n < 4 then
47.         begin
48.                 // store result
49.                 writeStr(intPrimeFactorization, n);
50.         end
51.         else
52.         begin
53.                 intPrimeFactorization := ipf();
54.         end;
55. end;
56.
57. // MAIN //
58. var
59.         n: qword;
60. begin