Problem:
Given a positive integer N, print all prime numbers upto N
Input Format:
positive integer N
Output Format:
prime numbers from 0 to N in new line
Constraints:
1<=N<=1000000Sample Input
20
Sample Output:
2
3
5
7
11
13
17
19
3
5
7
11
13
17
19
Explanations:
Solution:
use warnings;
chomp(my $n=<>);
if($n>1)
{
print "2\n";
}
my @arr=(2);
for (my $i=3; $i<=$n;$i+=2) {
my $isprime = 1;
my $c = sqrt($i) + 1;
foreach my $p (@arr) {
if ($p >= $c) {
last;
}
if ($i % $p == 0) {
$isprime = 0;
last;
}
}
if ($isprime == 1) {
print "$i\n";
push(@arr, $i);
}
}
Tips:
This algorithms is fastest method to print prime numbers upto 1000000