Danial Kosarifa Danial Kosarifa - 4 months ago 10
Swift Question

speed up prime number generating

I have written a program that generates prime numbers . It works well but I want to speed it up as it takes quite a while for generating the all the prime numbers till 10000

var list = [2,3]
var limitation = 10000
var flag = true
var tmp = 0

for (var count = 4 ; count <= limitation ; count += 1 ){


while(flag && tmp <= list.count - 1){
if (count % list[tmp] == 0){
flag = false

}else if ( count % list[tmp] != 0 && tmp != list.count - 1 ){
tmp += 1
}else if ( count % list[tmp] != 0 && tmp == list.count - 1 ){
list.append(count)

}
}
flag = true
tmp = 0
}

print(list)

Answer

In addition to what Nick already explained, you can also easily take advantage of the following property: all primes greater than 3 are congruent to 1 or -1 mod 6.

Because you've already included 2 and 3 in your initial list, you can therefore start with count = 6, test count - 1 and count + 1 and increment by 6 each time.

Below his is my first attempt either at Swift, so pardon the syntax which is probably far from optimal.

var list = [2,3]
var limitation = 10000
var flag = true
var tmp = 0
var max = 0

for(var count = 6 ; count <= limitation ; count += 6) {
  for(var d = -1; d <= 1; d += 2) {
    max = Int(floor(sqrt(Double(count + d))))

    for(flag = true, tmp = 0; flag && list[tmp] <= max; tmp++) {
      if((count + d) % list[tmp] == 0) {
        flag = false
      }
    }
    if(flag) {
      list.append(count + d)
    }
  }
}
print(list)

I've tested the above code on iswift.org/playground with limitation = 10,000, 100,000 and 1,000,000.