debianforum.de

prime_factorization.php

SNIPPET_DESC:

Primzahlenfaktorisierung in PHP

SNIPPET_CREATION_TIME:

05.12.2023 06:57:50

SNIPPET_PRUNE_TIME:

Unendlich

SNIPPET_TEXT:

1. <?php
2.  
3. function factorize_range($a, $b) {
4.         $factors = array();
5.         if ($a > $b) {
6.                 return $factors;
7.         }
8.         for ($i = $a; $i <= $b; $i++) {
9.                 $factors[$i] = factorize($i);
10.         }
11.         return $factors;
12. }
13.  
14. function factorize($x) {
15.         $factors = array();
16.         $primes = primes_up_to(sqrt($x));
17.         $n = count($primes);
18.         for ($i = 0; $x > 1 && $i < $n;) {
19.                 $prime = $primes[$i];
20.                 if ($x % $prime == 0) {
21.                         $factors[] = $prime;
22.                         $x /= $prime;
23.                 } else {
24.                         $i++;
25.                 }
26.         }
27.         if ($x > 1) {
28.                 $factors[] = $x;
29.         }
30.         return $factors;
31. }
32.  
33. function primes_up_to($n) {
34.         $primes = array();
35.         if ($n < 2) {
36.                 return $primes;
37.         }
38.         for ($i = 2; $i <= $n; $i++) {
39.                 if (is_prime($i)) {
40.                         $primes[] = $i;
41.                 }
42.         }
43.         return $primes;
44. }
45.  
46. function is_prime($x) {
47.         for ($i = 2; $i <= $x / 2; $i++) {
48.                 if ($x % $i == 0) {
49.                         return false;
50.                 }
51.         }
52.         return true;
53. }
54.  
55. header("Content-Type: text/plain");
56.  
57. if (!array_key_exists("lower", $_GET) || !array_key_exists("upper", $_GET)) {
58.         die("usage: ?lower=[lower]&upper=[upper]");
59. }
60.  
61. $result = factorize_range($_GET["lower"], $_GET["upper"]);
62. foreach ($result as $n => $fs) {
63.         echo("{$n}:\t");
64.         foreach ($fs as $f) {
65.                 echo("{$f} ");
66.         }
67.         echo("\n");
68. }
69.  
70. ?>
71.  

Quellcode

Hier kannst du den Code kopieren und ihn in deinen bevorzugten Editor einfügen. PASTEBIN_DOWNLOAD_SNIPPET_EXPLAIN