I am going to show you how I created the "Sieve of Eratosthenes" using PHP/MySQL. A very inefficient method when it comes to performance but an easy method when it comes to visualization. I wrote this program because I wanted to implement the algorithm in my own way.
Assume that we are to generate prime numbers less than or equal to n. Let n be equal to 1000 in the below example.
The following is going to be our approach:
The following is going to be our approach:
1) Create blocks numbered 2 to 1000 as shown below:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
.
.
.
1000
2) Start by removing the multiples (starting from 2) of the first prime number (let this be p) until the multiplier is greater than n/p (in this case 1000/2 = 500):
2 p
3
p X 2 = 4
5
p X 3 = 6 7
p X 4 = 8
9
p X 5 = 10
11
p X 6 = 12
13
p X 7 = 14
15
p X 8 = 16
17
p X 9 = 18
19
p X 10 = 20
.
.
.
p X 500 = 1000 (n)
Now take the next remaining number greater than p and assign this number to p.
3) Repeat the above step till p is equal to n. As a refinement, it is sufficient to stop when p is greater than √n; in this case when p is greater than 31.
4) Display all the remaining numbers. These are the prime numbers less than or equal to n:
2
3
5
7
11
13
17
19
.
.
.
997
What follows is going to be the crux of our PHP/MySQL logic: Think of the above blocks as rows in a MySQL table.
We will use PHP to perform all the above operations on a MySQL table.
Here is how:
1) Create a new table with one column for storing the numbers. The rows of this table will be the blocks containing the numbers. Create a primary key on this column for faster and efficient access.
2) INSERT (n - 1) rows into this table with integer values from 2 to n.
3) Start by deleting the rows having values of multiples (starting from 2) of the first prime number (assign this value to p). Run a SELECT query to get the value of the first row greater than p. Assign this row value to p.
4) Repeat the above step till p is greater than √n.
5) Run a SELECT query to get the values of all the rows in the table. These are the prime number less than or equal to n.
PHP/MySQL code for displaying prime numbers less than or equal to 1000:
<?php
function gen_prime($n) {
$link = mysqli_connect('localhost', 'root', 'my_password', 'my_db');
if (!$link) {
die('Connect Error (' . mysqli_connect_errno() . ') '. mysqli_connect_error());
}
mysqli_query($link, "CREATE TEMPORARY TABLE prime_numbers ( number int(11) NOT NULL, PRIMARY KEY (number));");
//Fill table with positive integers from 2 to $n with increments of 1
for ($i = 2; $i <= $n; $i++) {
$query_1 = "INSERT INTO prime_numbers (number) VALUES (".$i.")";
mysqli_query($link, $query_1);
}
$p = 2;
while ($p <= sqrt($n)){
//Delete numbers which are multiples of $p
for ($k = 2; $k <= ($n / $p); $k++) {
$query_2 = "DELETE FROM prime_numbers WHERE number = ".($p*$k);
mysqli_query($link, $query_2);
}
//Get the next row and assign it to $p
$query_3 = "SELECT number FROM prime_numbers WHERE number > ".$p." ORDER BY number ASC LIMIT 1";
$row_1 = mysqli_fetch_assoc(mysqli_query($link, $query_3));
$p = $row_1['number'];
}
$result = mysqli_query($link, "SELECT number FROM prime_numbers");
//Display values of remaining rows. These are prime numbers <= $n
while ($row_2 = mysqli_fetch_assoc($result)) {
echo $row_2['number']."<br/>";
}
mysqli_close($link);
}
gen_prime(1000);
?>
Disclaimers:
1) The code shown above is a basic working code of the logic under discussion. It lacks in many ways such as error checking, efficient coding standards etc. I know that you are looking for a microscope for reading the code. I apologize for this as it was the only way to post the code without skewing the formatting. You can copy this code to notepad and increase the font size to improve visibility.
2) This PHP/MySQL method is based entirely on my idea. If any part of it resembles anything found elsewhere, it is purely coincidental.
References:
1) Wikipedia, the free encyclopedia
References:
1) Wikipedia, the free encyclopedia
