Successive prime differences: Difference between revisions
Content added Content deleted
m (Put Sieve of Eratosthenes implementation in separate header file) |
|||
Line 775: | Line 775: | ||
[6, 4, 2] 306 [31, 37, 41, 43]...[997141, 997147, 997151, 997153] |
[6, 4, 2] 306 [31, 37, 41, 43]...[997141, 997147, 997151, 997153] |
||
</pre> |
</pre> |
||
=={{header|Kotlin}}== |
|||
{{trans|Java}} |
|||
<lang scala>private fun sieve(limit: Int): Array<Int> { |
|||
val primes = mutableListOf<Int>() |
|||
primes.add(2) |
|||
val c = BooleanArray(limit + 1) // composite = true |
|||
// no need to process even numbers > 2 |
|||
var p = 3 |
|||
while (true) { |
|||
val p2 = p * p |
|||
if (p2 > limit) { |
|||
break |
|||
} |
|||
var i = p2 |
|||
while (i <= limit) { |
|||
c[i] = true |
|||
i += 2 * p |
|||
} |
|||
do { |
|||
p += 2 |
|||
} while (c[p]) |
|||
} |
|||
var i = 3 |
|||
while (i <= limit) { |
|||
if (!c[i]) { |
|||
primes.add(i) |
|||
} |
|||
i += 2 |
|||
} |
|||
return primes.toTypedArray() |
|||
} |
|||
private fun successivePrimes(primes: Array<Int>, diffs: Array<Int>): List<List<Int>> { |
|||
val results = mutableListOf<List<Int>>() |
|||
val dl = diffs.size |
|||
outer@ for (i in 0 until primes.size - dl) { |
|||
val group = IntArray(dl + 1) |
|||
group[0] = primes[i] |
|||
for (j in i until i + dl) { |
|||
if (primes[j + 1] - primes[j] != diffs[j - i]) { |
|||
continue@outer |
|||
} |
|||
group[j - i + 1] = primes[j + 1] |
|||
} |
|||
results.add(group.toList()) |
|||
} |
|||
return results |
|||
} |
|||
fun main() { |
|||
val primes = sieve(999999) |
|||
val diffsList = arrayOf( |
|||
arrayOf(2), |
|||
arrayOf(1), |
|||
arrayOf(2, 2), |
|||
arrayOf(2, 4), |
|||
arrayOf(4, 2), |
|||
arrayOf(6, 4, 2) |
|||
) |
|||
println("For primes less than 1,000,000:-\n") |
|||
for (diffs in diffsList) { |
|||
println(" For differences of ${diffs.contentToString()} ->") |
|||
val sp = successivePrimes(primes, diffs) |
|||
if (sp.isEmpty()) { |
|||
println(" No groups found") |
|||
continue |
|||
} |
|||
println(" First group = ${sp[0].toTypedArray().contentToString()}") |
|||
println(" Last group = ${sp[sp.size - 1].toTypedArray().contentToString()}") |
|||
println(" Number found = ${sp.size}") |
|||
println() |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre>For primes less than 1,000,000:- |
|||
For differences of [2] -> |
|||
First group = [3, 5] |
|||
Last group = [999959, 999961] |
|||
Number found = 8169 |
|||
For differences of [1] -> |
|||
First group = [2, 3] |
|||
Last group = [2, 3] |
|||
Number found = 1 |
|||
For differences of [2, 2] -> |
|||
First group = [3, 5, 7] |
|||
Last group = [3, 5, 7] |
|||
Number found = 1 |
|||
For differences of [2, 4] -> |
|||
First group = [5, 7, 11] |
|||
Last group = [999431, 999433, 999437] |
|||
Number found = 1393 |
|||
For differences of [4, 2] -> |
|||
First group = [7, 11, 13] |
|||
Last group = [997807, 997811, 997813] |
|||
Number found = 1444 |
|||
For differences of [6, 4, 2] -> |
|||
First group = [31, 37, 41, 43] |
|||
Last group = [997141, 997147, 997151, 997153] |
|||
Number found = 306</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |