Danial Kosarifa - 3 months ago 8

Swift Question

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.

Source (Stackoverflow)

Comments