Cuban primes: Difference between revisions
Content deleted Content added
Line 1,346: | Line 1,346: | ||
which took 31 seconds to calculate. |
which took 31 seconds to calculate. |
||
</pre> |
</pre> |
||
=={{header|Scala}}== |
|||
In this example, we start by building an infinite lazy list of cubans and filter out non-primes. This gives us a lazily evaluated list of all cuban primes, and finding the first 200 simply involves taking 200 elements off the list. |
|||
To find the 100,000th cuban prime, performance becomes an issue. To remedy this, we write a function that breaks off a chunk from the front of the list of cubans and filters it using a parallel vector, repeating this process until it's found enough cuban primes. This allows us to benefit from the memory efficiency of lazy lists and the number-crunching speed of parallel vectors at the same time. |
|||
Spire's SafeLong is used instead of Java's BigInt for performance. |
|||
<lang scala>import spire.math.SafeLong |
|||
import spire.implicits._ |
|||
import scala.annotation.tailrec |
|||
import scala.collection.parallel.immutable.ParVector |
|||
object CubanPrimes { |
|||
def main(args: Array[String]): Unit = { |
|||
println(formatTable(cubanPrimes.take(200).toVector, 10)) |
|||
println(f"The 100,000th cuban prime is: ${getNthCubanPrime(100000).toBigInt}%,d") |
|||
} |
|||
def cubanPrimes: LazyList[SafeLong] = cubans.filter(isPrime) |
|||
def cubans: LazyList[SafeLong] = LazyList.iterate(SafeLong(0))(_ + 1).map(n => (n + 1).pow(3) - n.pow(3)) |
|||
def isPrime(num: SafeLong): Boolean = (num > 1) && !(SafeLong(2) #:: LazyList.iterate(SafeLong(3)){n => n + 2}).takeWhile(n => n*n <= num).exists(num%_ == 0) |
|||
def getNthCubanPrime(num: Int): SafeLong = { |
|||
@tailrec |
|||
def nHelper(rem: Int, src: LazyList[SafeLong]): SafeLong = { |
|||
val cprimes = src.take(100000).to(ParVector).filter(isPrime) |
|||
if(cprimes.size < rem) nHelper(rem - cprimes.size, src.drop(100000)) |
|||
else cprimes.toVector.sortWith(_<_)(rem - 1) |
|||
} |
|||
nHelper(num, cubans) |
|||
} |
|||
def formatTable(lst: Vector[SafeLong], rlen: Int): String = { |
|||
@tailrec |
|||
def fHelper(ac: Vector[String], src: Vector[String]): String = { |
|||
if(src.nonEmpty) fHelper(ac :+ src.take(rlen).mkString, src.drop(rlen)) |
|||
else ac.mkString("\n") |
|||
} |
|||
val maxLen = lst.map(n => f"${n.toBigInt}%,d".length).max |
|||
val formatted = lst.map(n => s"%,${maxLen + 2}d".format(n.toInt)) |
|||
fHelper(Vector[String](), formatted) |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> 7 19 37 61 127 271 331 397 547 631 |
|||
919 1,657 1,801 1,951 2,269 2,437 2,791 3,169 3,571 4,219 |
|||
4,447 5,167 5,419 6,211 7,057 7,351 8,269 9,241 10,267 11,719 |
|||
12,097 13,267 13,669 16,651 19,441 19,927 22,447 23,497 24,571 25,117 |
|||
26,227 27,361 33,391 35,317 42,841 45,757 47,251 49,537 50,311 55,897 |
|||
59,221 60,919 65,269 70,687 73,477 74,419 75,367 81,181 82,171 87,211 |
|||
88,237 89,269 92,401 96,661 102,121 103,231 104,347 110,017 112,327 114,661 |
|||
115,837 126,691 129,169 131,671 135,469 140,617 144,541 145,861 151,201 155,269 |
|||
163,567 169,219 170,647 176,419 180,811 189,757 200,467 202,021 213,067 231,019 |
|||
234,361 241,117 246,247 251,431 260,191 263,737 267,307 276,337 279,991 283,669 |
|||
285,517 292,969 296,731 298,621 310,087 329,677 333,667 337,681 347,821 351,919 |
|||
360,187 368,551 372,769 374,887 377,011 383,419 387,721 398,581 407,377 423,001 |
|||
436,627 452,797 459,817 476,407 478,801 493,291 522,919 527,941 553,411 574,219 |
|||
584,767 590,077 592,741 595,411 603,457 608,851 611,557 619,711 627,919 650,071 |
|||
658,477 666,937 689,761 692,641 698,419 707,131 733,591 742,519 760,537 769,627 |
|||
772,669 784,897 791,047 812,761 825,301 837,937 847,477 863,497 879,667 886,177 |
|||
895,987 909,151 915,769 925,741 929,077 932,419 939,121 952,597 972,991 976,411 |
|||
986,707 990,151 997,057 1,021,417 1,024,921 1,035,469 1,074,607 1,085,407 1,110,817 1,114,471 |
|||
1,125,469 1,155,061 1,177,507 1,181,269 1,215,397 1,253,887 1,281,187 1,285,111 1,324,681 1,328,671 |
|||
1,372,957 1,409,731 1,422,097 1,426,231 1,442,827 1,451,161 1,480,519 1,484,737 1,527,247 1,570,357 |
|||
The 100,000th cuban prime is: 1,792,617,147,127</pre> |
|||
=={{header|Sidef}}== |
=={{header|Sidef}}== |