RUET-OJ/sieve.php at master · shawon100/RUET-OJ · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
<?php

$n=200000;

 $a=array();
 $p=array();


function sieve()
{
   $k=1;
   global $n;
   global $a;
   global $p;

    for($i=1;$i<=$n;$i++)
    {
    	$a[$i]=0;
    }

    for($i=1;$i<=$n;$i++)
    {
    	$p[$i]=0;
    }


	$a[0]=1;
	$a[1]=1;


	for($i=2;$i<=$n;$i=$i+2)
	{
		$a[$i]=1;
	}
	for($i=3;$i<=sqrt($n);$i=$i+2)
	{
		for($j=$i*$i; $j<=$n;$j=$j+$i*2)
		{
			$a[$j]=1;
		}
	}
	for($i=2;$i<=$n;$i++)
	{
		if($a[$i]== 0)
		{
			$p[$k]=$i;

			$k++;

		}
	}
}

sieve();

echo("Generated Prime Numbers (1 to n) By Sieve Algorithm <br><br>");

for($m=1;$m<=$n;$m++)
{

   if($p[$m]==0)
   {

      break;
      //error_reporting(0);
   }
   echo($p[$m]."<br>");


}


?>