Print prime numbers in a range using for loop in Julia

Viewed 526

I'm learning Julia syntax and I'm new to coding in general. I'm looking for a way to print all prime numbers within a given range using a for loop and if statement. (Something like this).

for num in 1:100
    if num > 1
        for i in 1:(num)
            if (num % i) == 0
                print(num)
            end
        end
    end
end
3 Answers

In case you're interested, here's an alternative solution based on the Sieve of Eratosthenes:

UPPERLIMIT = 100

#=
Create an array of booleans called "is_prime" which is initially true
for all odd numbers, false for all even numbers
=#
is_prime = [(i % 2) > 0 for i in 1:UPPERLIMIT]
is_prime[2] = true  # 2 is the exception, an even prime

#=
Now iterate through the array up to the square root of UPPERLIMIT.
factors which are bigger than sqrt(UPPERLIMIT) must have co-factors
that are smaller, so there's no need to search above that limit.
=#
for num in 3:2:floor(Int,sqrt(UPPERLIMIT))
    #=
    Every time we find a prime, wipe out all of its multiples.
    We can start at 3*num since 2*num is already masked out
    because it's even.  Adding odd multiples would also yield
    even outcomes, so they can be stepped over as well.
    =#
    if is_prime[num]
        for i in 3*num:2*num:UPPERLIMIT
            is_prime[i] = false
        end
    end
end

# Everything that hasn't been masked out to false is now prime!
for i in 2:UPPERLIMIT
    if is_prime[i]
        println(i)
    end
end

Note that this is almost the same number of lines of actual code (after stripping out comments) as the brute force approach. Both produce identical results, but this version is substantially faster - 2.1s vs 67s to generate the 664579 primes up to 10_000_000 on my laptop.


ADDENDUM

I'm new to Julia myself, and have been learning as I played with this. That led to the version below, where I replaced conditional loops with && and foreach. I've removed the comments to highlight how little code is required:

UPPERLIMIT = 100

is_prime = [(i % 2) > 0 for i in 1:UPPERLIMIT]
is_prime[2] = true  # 2 is the exception, an even prime

for num in 3:2:floor(Int,sqrt(UPPERLIMIT))
    is_prime[num] && foreach(i -> is_prime[i] = false, num*num:2*num:UPPERLIMIT)
end

foreach(i -> is_prime[i] && println(i), 2:UPPERLIMIT)

This variant not only involves less code, but it runs even faster—1.41s vs 2.1s to generate primes up to 10M.

Using your explicit check of candidate divisors approach, how about the following? I've annotated with comments rather than writing verbiage before or after the code:

# 2 is a special case, just print it
println(2)

for num in 3:2:100  # step sizes of 2 starting from 3, only need to check odd numbers now
    prime_candidate = true  # consider everything prime until proven otherwise
    for i in 3:2:floor(Int,sqrt(num))  # no need to check 1, num itself, or even numbers
        if (num % i) == 0   # divisible by a smaller number?
            prime_candidate = false # mark it not prime...
            break   # ...and we're outta here!
        end
    end
    if prime_candidate  # if the boolean hasn't been flipped by now, it's prime
        println(num)
    end
end

Thanks to Oscar Smith for the suggestion to change the check range to sqrt(num). Suppose num is evenly divisible by i. Then it must have a cofactor j such that i * j = num. If both i and j were to be bigger than sqrt(num), then their product would be bigger than num, so it follows that one of i or j must be ≤ sqrt(num). Consequently, if you haven't found a factor by the time you get to sqrt(num), then num has no integer factors and must be prime so you can stop searching.

The Primes package has an isprime function which uses the Miller-Rabin primality test (https://en.wikipedia.org/wiki/Miller–Rabin_primality_test).

So you could do:

import Primes

for num in 1:100
  Primes.isprime(num) ? println(num) : nothing
end

If you just want an array of those numbers that are prime within a range, you could do that with:

filter(Primes.isprime, 1:100)

If you don't already have the Primes package, you can add it like so:

import Pkg
Pkg.add("Primes")
Related