Lazarus

Free Pascal => Beginners => Topic started by: RubenMG on February 12, 2018, 05:31:00 pm

Title: Variables related question.
Post by: RubenMG 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.  
  27. readLn();
  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.

Title: Re: Variables related question.
Post by: Blaazen on February 12, 2018, 06:46:29 pm
Input is 13195 and output of your program should be 29*455 ?
Title: Re: Variables related question.
Post by: RubenMG on February 12, 2018, 06:47:58 pm
Hi!

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

Bye!
Title: Re: Variables related question.
Post by: Bart 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 (https://en.wikipedia.org/wiki/Sieve_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 (http://svn.code.sf.net/p/flyingsheep/code/trunk/MijnLib/primes.pp) as a starting point.

Bart
Title: Re: Variables related question.
Post by: RubenMG 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 (https://en.wikipedia.org/wiki/Sieve_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 (http://svn.code.sf.net/p/flyingsheep/code/trunk/MijnLib/primes.pp) as a starting point.

Bart

Thanks for your info.

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.
Title: Re: Variables related question.
Post by: howardpc 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.  
  83.   ReadLn;
  84. end.
Title: Re: Variables related question.
Post by: Bart 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 5
The product of the prime factors of 60 is 30

Bart
Title: Re: Variables related question.
Post by: Kays 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
  61.         readLn(n);
  62.         writeLn(intPrimeFactorization(n));
  63. end.
TinyPortal © 2005-2018