Danial Kosarifa - 1 year ago 119
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)
``````

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download