Working through nested loops

Question

Is there a way to find all the primes between 0 to 100 without actually using nested loops, i.e. with time complexity of less than n^2. I did try recursion but it still is same with same complexity. can anyone help please. Thanks

Answer 1

A very useful implementation is to pre-calculate the list.

my @primes = (
   2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
   43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
);

say for @primes;

Obvious? Maybe, but I bet many people are about to post far more complex, and slower solutions.

Answer 2

Yes, look at the Seive of Atkin, which is an optimized version of the Sieve of Eratosthenes.

Python implementation:

import math

def sieveOfAtkin(limit):
    P = [2,3]
    sieve=[False]*(limit+1)
    for x in range(1,int(math.sqrt(limit))+1):
        for y in range(1,int(math.sqrt(limit))+1):
            n = 4*x**2 + y**2
            if n<=limit and (n%12==1 or n%12==5) : sieve[n] = not sieve[n]
            n = 3*x**2+y**2
            if n<= limit and n%12==7 : sieve[n] = not sieve[n]
            n = 3*x**2 - y**2
            if x>y and n<=limit and n%12==11 : sieve[n] = not sieve[n]
    for x in range(5,int(math.sqrt(limit))):
        if sieve[x]:
            for y in range(x**2,limit+1,x**2):
                sieve[y] = False
    for p in range(5,limit):
        if sieve[p] : P.append(p)
    return P

print sieveOfAtkin(100)

Answer 3

Not exactly improvement from O(n^2) But you can narrow down your search like this: Prime numbers > 6 have a property. They are either 6n+1 or 6n-1(It does not mean that all 6n+1 or 6n-1s are prime numbers) So your code would look like:

/** * @author anirbanroy */

object PrimeNumberPrinter {

def main(args: Array[String]) {
var count: Int = 0
var initialPrimeNumberCount: Array[Int] = Array(0, 0, 1, 2, 2)
println("Enter a range: ")
val input = io.StdIn.readInt()
if (input > 4) {
  count = 2;
  for (i <- 5 to input by 6) {
    if (i + 2 <= input) {
      if (isPrime(i + 2)) {
        count = count + 1
      }
    }
    if (i <= input) {
      if (isPrime(i)) {
        count = count + 1
      }
    }
  }

  println("No of prime numbers: " + count)

} else {
  println("No of prime numbers are: " + initialPrimeNumberCount(input))
}

}

def isPrime(value: Int): Boolean = {
val range: Int = round(sqrt(value).toFloat)
 for (j <- 2 to range) {
   if (value.%(j) == 0)
     return false
  }
  return true
}

Answer 4

The brute force solution (trying to divide all odd integers by all odd divisors) doesn't have complexity O(N²), but O(N√N), as the search can stop when a tentative divisor exceeding √N has been reached.

You can pretty easily reduce this complexity by using the primes already identified, rather than all odd integers. Given the density function of the primes, you reduce to O(N√N/Log(N)).

Anyway, for N as small as 100, this "optimization" is not at all significant, as √N is only 10 and the prime divisors to be considered are 3, 5, 7, whereas the odd divisors would be 3, 5, 7, 9.

Here is a simple implementation that tries three divisors and does not attempt to stop when i>√N as this would add costly conditional branches.

N= 100
print 2, 3, 5, 7,
for i in range(3, N, 2):
    if i % 3 != 0 and i % 5 != 0 and i % 7 != 0:
        print i,

Technically speaking, this code is pure O(N), but only works until N<121. By direct counting, it performs exactly 106 modulo operations when using the shortcut evaluation of the and's.