Quiz 81: Print prime numbers upto N where 1<=N<=1000000

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<=1000000

Sample Input

20

Sample Output:

2
3
5
7
11
13
17
19

Explanations:

Prime numbers upto 20

---

Solution:

use strict;
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