Cuban primes: Difference between revisions
m (changed some spellings of "cuban" (should be lower case) in some comments (but not any programs)..) |
m (uncased various in sourcecode & output of C++, C#, & VB.NET) |
||
Line 38: | Line 38: | ||
#include <climits> |
#include <climits> |
||
#include <cmath> |
#include <cmath> |
||
using namespace std; |
using namespace std; |
||
vector <long long> primes; |
vector <long long> primes{ 3, 5 }; |
||
int main() |
int main() |
||
{ |
{ |
||
cout.imbue(locale("")); |
cout.imbue(locale("")); |
||
const int cutOff = 200 |
const int cutOff = 200, bigUn = 100000, |
||
⚫ | |||
const int bigUn = 100000; |
|||
const char tn[] = " cuban prime"; |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
int c = 0; |
int c = 0; |
||
bool showEach = true; |
bool showEach = true; |
||
long long |
long long u = 0, v = 1; |
||
auto st = chrono::system_clock::now(); |
auto st = chrono::system_clock::now(); |
||
for (long long i = 1; i <= LLONG_MAX; i++) |
for (long long i = 1; i <= LLONG_MAX; i++) |
||
{ |
{ |
||
⚫ | |||
bool found = false; |
bool found = false; |
||
long long mx = (long long)(ceil(sqrt(v += (u += 6)))); |
|||
for(long long item : primes) |
for (long long item : primes) |
||
{ |
{ |
||
if (item > mx) break; |
if (item > mx) break; |
||
Line 81: | Line 78: | ||
if (!fnd) primes.push_back(z); |
if (!fnd) primes.push_back(z); |
||
} |
} |
||
primes.push_back(v); |
primes.push_back(v); cout.width(11); cout << v; |
||
if (c % 10 == 0) cout << |
if (c % 10 == 0) cout << endl; |
||
if (c == cutOff) |
if (c == cutOff) |
||
{ |
{ |
||
showEach = false; |
showEach = false; |
||
cout << "\nProgress to the " << bigUn << "th |
cout << "\nProgress to the " << bigUn << "th" << tn << ": "; |
||
} |
} |
||
} |
} |
||
Line 92: | Line 89: | ||
} |
} |
||
} |
} |
||
cout << "\nThe " << c << "th" << tn << " is " << v; |
|||
chrono::duration<double> elapsed_seconds = chrono::system_clock::now() - st; |
|||
chrono::duration<double> elapsed_seconds = end - st; |
|||
cout << "\nComputation time was " << elapsed_seconds.count() << " seconds" << endl; |
cout << "\nComputation time was " << elapsed_seconds.count() << " seconds" << endl; |
||
return 0; |
return 0; |
||
}</lang> |
}</lang> |
||
{{out}} |
{{out}} |
||
<pre>The first 200 |
<pre>The first 200 cuban primes: |
||
7 19 37 61 127 271 331 397 547 631 |
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 |
919 1,657 1,801 1,951 2,269 2,437 2,791 3,169 3,571 4,219 |
||
Line 121: | Line 117: | ||
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 |
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 |
||
Progress to the 100,000th |
Progress to the 100,000th cuban prime: .................................................. |
||
The 100,000th |
The 100,000th cuban prime is 1,792,617,147,127 |
||
Computation time was |
Computation time was 35.5644 seconds</pre> |
||
=={{header|C#}}== |
=={{header|C#}}== |
||
Line 134: | Line 130: | ||
static class Program |
static class Program |
||
{ |
{ |
||
static List<long> primes = new List<long>(); |
static List<long> primes = new List<long>() { 3, 5 }; |
||
static void Main(string[] args) |
static void Main(string[] args) |
||
Line 142: | Line 138: | ||
const int chunks = 50; |
const int chunks = 50; |
||
const int little = bigUn / chunks; |
const int little = bigUn / chunks; |
||
const string tn = " cuban prime"; |
|||
Console.WriteLine("The first {0:n0}{1}s:", cutOff, tn); |
|||
int c = 0; |
int c = 0; |
||
bool showEach = true; |
bool showEach = true; |
||
long |
long u = 0, v = 1; |
||
DateTime st = DateTime.Now; |
DateTime st = DateTime.Now; |
||
for (long i = 1; i <= long.MaxValue; i++) |
for (long i = 1; i <= long.MaxValue; i++) |
||
{ |
{ |
||
⚫ | |||
bool found = false; |
bool found = false; |
||
int mx = System.Convert.ToInt32(Math.Ceiling(Math.Sqrt(v))); |
int mx = System.Convert.ToInt32(Math.Ceiling(Math.Sqrt(v += (u += 6)))); |
||
foreach ( |
foreach (long item in primes) |
||
{ |
{ |
||
if (item > mx) break; |
if (item > mx) break; |
||
Line 165: | Line 160: | ||
{ |
{ |
||
bool fnd = false; |
bool fnd = false; |
||
foreach ( |
foreach (long item in primes) |
||
{ |
{ |
||
if (item > mx) break; |
if (item > mx) break; |
||
Line 177: | Line 172: | ||
{ |
{ |
||
showEach = false; |
showEach = false; |
||
Console.Write("\nProgress to the {0:n0}th |
Console.Write("\nProgress to the {0:n0}th{1}: ", bigUn, tn); |
||
} |
} |
||
} |
} |
||
Line 183: | Line 178: | ||
} |
} |
||
} |
} |
||
Console.WriteLine("\nThe {1:n0}th |
Console.WriteLine("\nThe {1:n0}th{2} is {0,17:n0}", v, c, tn); |
||
Console.WriteLine("Computation time was {0} seconds", (DateTime.Now - st).TotalSeconds); |
Console.WriteLine("Computation time was {0} seconds", (DateTime.Now - st).TotalSeconds); |
||
if (System.Diagnostics.Debugger.IsAttached) Console.ReadKey(); |
if (System.Diagnostics.Debugger.IsAttached) Console.ReadKey(); |
||
Line 189: | Line 184: | ||
}</lang> |
}</lang> |
||
{{out}} |
{{out}} |
||
<pre>The first 200 |
<pre>The first 200 cuban primes: |
||
7 19 37 61 127 271 331 397 547 631 |
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 |
919 1,657 1,801 1,951 2,269 2,437 2,791 3,169 3,571 4,219 |
||
Line 211: | Line 206: | ||
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 |
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 |
||
Progress to the 100,000th |
Progress to the 100,000th cuban prime: .................................................. |
||
The 100,000th |
The 100,000th cuban prime is 1,792,617,147,127 |
||
Computation time was |
Computation time was 63.578673 seconds</pre> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
Line 665: | Line 660: | ||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
===Corner Cutting Version=== |
===Corner Cutting Version=== |
||
This language doesn't have a built-in for a ''IsPrime()'' function, so I was surprised to find that this runs so quickly. It builds a list of primes while it is creating the table. Since the last item on the table is larger than the square root of the 100,000th cuban prime, there is no need to continue adding to the prime list while checking up to the 100,000th cuban prime. I found a bit of a shortcut, if you skip the iterator by just the right amount, only one value is tested for the final result. It's hard-coded in the program, so if another final cuban prime were to be selected for output, the program would need a re-write. If not skipping ahead to the answer, it takes a few seconds over a minute to eventually get to it (see Snail Version below). |
This language doesn't have a built-in for a ''IsPrime()'' function, so I was surprised to find that this runs so quickly. It builds a list of primes while it is creating the output table. Since the last item on the table is larger than the square root of the 100,000th cuban prime, there is no need to continue adding to the prime list while checking up to the 100,000th cuban prime. I found a bit of a shortcut, if you skip the iterator by just the right amount, only one value is tested for the final result. It's hard-coded in the program, so if another final cuban prime were to be selected for output, the program would need a re-write. If not skipping ahead to the answer, it takes a few seconds over a minute to eventually get to it (see Snail Version below). |
||
<lang vbnet>Module Module1 |
<lang vbnet>Module Module1 |
||
Dim primes As |
Dim primes As List(Of Long) = {3L, 5L}.ToList() |
||
Sub Main(args As String()) |
Sub Main(args As String()) |
||
Const cutOff As Integer = 200, bigUn As Integer = 100000 |
Const cutOff As Integer = 200, bigUn As Integer = 100000, |
||
tn As String = " cuban prime" |
|||
primes.Add(3) : primes.Add(5) |
|||
Console.WriteLine("The first {0:n0} |
Console.WriteLine("The first {0:n0}{1}s:", cutOff, tn) |
||
Dim c As Integer = 0, showEach As Boolean = True, skip As Boolean = True, |
Dim c As Integer = 0, showEach As Boolean = True, skip As Boolean = True, |
||
v As Long = 0, st As DateTime = DateTime.Now |
v As Long = 0, st As DateTime = DateTime.Now |
||
Line 698: | Line 693: | ||
End If |
End If |
||
Next |
Next |
||
Console.WriteLine("{1}The {2:n0}th |
Console.WriteLine("{1}The {2:n0}th{3} is {0,17:n0}", v, vbLf, c, tn) |
||
Console.WriteLine("Computation time was {0} seconds", (DateTime.Now - st).TotalSeconds) |
Console.WriteLine("Computation time was {0} seconds", (DateTime.Now - st).TotalSeconds) |
||
If System.Diagnostics.Debugger.IsAttached Then Console.ReadKey() |
If System.Diagnostics.Debugger.IsAttached Then Console.ReadKey() |
||
Line 704: | Line 699: | ||
End Module</lang> |
End Module</lang> |
||
{{out}} |
{{out}} |
||
<pre>The first 200 |
<pre>The first 200 cuban primes: |
||
7 19 37 61 127 271 331 397 547 631 |
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 |
919 1,657 1,801 1,951 2,269 2,437 2,791 3,169 3,571 4,219 |
||
Line 726: | Line 721: | ||
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 |
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 |
The 100,000th cuban prime is 1,792,617,147,127 |
||
Computation time was 0. |
Computation time was 0.2989494 seconds</pre> |
||
===Snail Version=== |
===Snail Version=== |
||
This one doesn't take any shortcuts. It could be sped up (Execution time about 15 seconds) by threading chunks of the search for the 100,000th cuban prime, but you would have to take a guess about how far to go, which would be hard-coded, so one might as well use the short-cut version if you are willing to overlook that difficulty. |
This one doesn't take any shortcuts. It could be sped up (Execution time about 15 seconds) by threading chunks of the search for the 100,000th cuban prime, but you would have to take a guess about how far to go, which would be hard-coded, so one might as well use the short-cut version if you are willing to overlook that difficulty. |
||
<lang vbnet> |
<lang vbnet>'Imports System.Threading.Tasks |
||
⚫ | |||
'Module Program |
|||
⚫ | |||
' Dim ic As Long = 0 |
|||
' Function tabulate(i As Long, amt As Integer) As Integer |
|||
' tabulate = 0 |
|||
' For j As Long = i To i + amt - 1 |
|||
⚫ | |||
' Dim found As Boolean = False, mx As Integer = Math.Ceiling(Math.Sqrt(v)) |
|||
' For Each item In primes |
|||
' If item > mx Then Exit For |
|||
' If v Mod item = 0 Then found = True : Exit For |
|||
' Next : If Not found Then tabulate += 1 |
|||
' Next : Console.Write(".") |
|||
' End Function |
|||
' Sub Main(args As String()) |
|||
' Dim taskList As New List(Of Task(Of Integer)) |
|||
' Const cutOff As Integer = 200, bigUn As Integer = 100000, |
|||
' chunks As Integer = 50 |
|||
⚫ | |||
⚫ | |||
' Dim c As Integer = 0, showEach As Boolean = True, para As Boolean = True |
|||
' Dim v As Long = 0 |
|||
' Dim st As DateTime = DateTime.Now |
|||
' For i As Long = 1 To Long.MaxValue |
|||
⚫ | |||
' Dim found As Boolean = False, mx As Integer = Math.Ceiling(Math.Sqrt(v)) |
|||
' For Each item In primes |
|||
' If item > mx Then Exit For |
|||
' If v Mod item = 0 Then found = True : Exit For |
|||
' Next : If Not found Then |
|||
' c += 1 : If showEach Then |
|||
' For z = primes.Last + 2 To v - 2 Step 2 |
|||
' Dim fnd As Boolean = False |
|||
' For Each item In primes |
|||
' If item > mx Then Exit For |
|||
' If z Mod item = 0 Then fnd = True : Exit For |
|||
' Next : If Not fnd Then primes.Add(z) |
|||
' Next : primes.Add(v) : Console.Write("{0,11:n0}", v) |
|||
' If c Mod 10 = 0 Then Console.WriteLine() |
|||
' If c = cutOff Then showEach = False : _ |
|||
' Console.Write("{0}Progress to the {1:n0}th Cuban prime: ", vbLf, bigUn) |
|||
' Else |
|||
' If para Then |
|||
' Const shortCutDistance As Integer = 770000 |
|||
' Dim amt As Integer = shortCutDistance / chunks |
|||
' For ii As Integer = 0 To shortCutDistance - 1 Step amt |
|||
' Dim ti As Integer = If(ii = 0, i + 1, ii), |
|||
' ta As Integer = If(ii = 0, amt - i - 1, amt) |
|||
' taskList.Add(Task.Run(Function() tabulate(ti, ta))) |
|||
' Next |
|||
' Task.WhenAll(taskList) |
|||
' For Each item In taskList.Select(Function(t) t.Result) |
|||
' c += item : Next |
|||
' para = False : i = shortCutDistance - 1 |
|||
' End If |
|||
' End If |
|||
' If c = bigUn Then Exit For |
|||
' End If |
|||
' Next |
|||
' Console.WriteLine("{1}The {2:n0}th Cuban prime is {0,17:n0}", v, vbLf, c) |
|||
' Console.WriteLine("Computation time was {0} seconds", (DateTime.Now - st).TotalSeconds) |
|||
' If System.Diagnostics.Debugger.IsAttached Then Console.ReadKey() |
|||
' End Sub |
|||
'End Module |
|||
Module Program |
|||
Dim primes As List(Of Long) = {3L, 5L}.ToList() |
|||
Sub Main(args As String()) |
Sub Main(args As String()) |
||
Dim taskList As New List(Of Task(Of Integer)) |
Dim taskList As New List(Of Task(Of Integer)) |
||
Const cutOff As Integer = 200, bigUn As Integer = 100000, |
Const cutOff As Integer = 200, bigUn As Integer = 100000, |
||
chunks As Integer = 50, little As Integer = bigUn / chunks |
chunks As Integer = 50, little As Integer = bigUn / chunks, |
||
tn As String = " cuban prime" |
|||
⚫ | |||
Console.WriteLine("The first {0:n0}{1}s:", cutOff, tn) |
|||
Dim c As Integer = 0, showEach As Boolean = True |
Dim c As Integer = 0, showEach As Boolean = True, |
||
u As Long = 0, v As Long = 1, |
|||
st As DateTime = DateTime.Now |
|||
For i As Long = 1 To Long.MaxValue |
For i As Long = 1 To Long.MaxValue |
||
u += 6 : v += u |
|||
Dim found As Boolean = False, mx As Integer = Math.Ceiling(Math.Sqrt(v)) |
Dim found As Boolean = False, mx As Integer = Math.Ceiling(Math.Sqrt(v)) |
||
For Each item In primes |
For Each item In primes |
||
Line 759: | Line 825: | ||
If c Mod 10 = 0 Then Console.WriteLine() |
If c Mod 10 = 0 Then Console.WriteLine() |
||
If c = cutOff Then showEach = False : _ |
If c = cutOff Then showEach = False : _ |
||
Console.Write("{0}Progress to the {1:n0}th |
Console.Write("{0}Progress to the {1:n0}th{2}: ", vbLf, bigUn, tn) |
||
End If |
End If |
||
If c Mod little = 0 Then Console.Write(".") : If c = bigUn Then Exit For |
If c Mod little = 0 Then Console.Write(".") : If c = bigUn Then Exit For |
||
End If |
End If |
||
Next |
Next |
||
Console.WriteLine("{1}The {2:n0}th |
Console.WriteLine("{1}The {2:n0}th{3} is {0,17:n0}", v, vbLf, c, tn) |
||
Console.WriteLine("Computation time was {0} seconds", (DateTime.Now - st).TotalSeconds) |
Console.WriteLine("Computation time was {0} seconds", (DateTime.Now - st).TotalSeconds) |
||
If System.Diagnostics.Debugger.IsAttached Then Console.ReadKey() |
If System.Diagnostics.Debugger.IsAttached Then Console.ReadKey() |
||
Line 770: | Line 836: | ||
End Module</lang> |
End Module</lang> |
||
{{out}} |
{{out}} |
||
<pre>The first 200 |
<pre>The first 200 cuban primes: |
||
7 19 37 61 127 271 331 397 547 631 |
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 |
919 1,657 1,801 1,951 2,269 2,437 2,791 3,169 3,571 4,219 |
||
Line 792: | Line 858: | ||
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 |
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 |
||
Progress to the 100,000th |
Progress to the 100,000th cuban prime: .................................................. |
||
The 100,000th |
The 100,000th cuban prime is 1,792,617,147,127 |
||
Computation time was |
Computation time was 49.5868152 seconds</pre> |
Revision as of 16:03, 2 February 2019
The name cuban has nothing to do with Cuba, but has to do with the fact that cubes (3rd powers) play a role in its definition.
- Some definitions of cuban primes
-
- primes which are the difference of two consecutive cubes.
- primes of the form: (n+1)3 - n3.
- primes of the form: n3 - (n-1)3.
- primes p such that n2(p+n) is a cube for some n>0.
- primes p such that 4p = 1 + 3n2.
Cuban primes were named in 1923 by Allan Joseph Champneys Cunningham.
- Task requirements
-
- show the first 200 cuban primes (in a multi─line horizontal format).
- show the 100,000th cuban prime.
- show all cuban primes with commas.
- show all output here.
Note that cuban prime isn't capitalized (as it doesn't refer to Cuba).
- Also see
-
- MathWorld entry: cuban prime.
- The OEIS entry: A2407. The 100,000th cuban prime can be verified in the 2nd example on this OEIS web page.
C++
<lang Cpp>#include <iostream>
- include <vector>
- include <chrono>
- include <climits>
- include <cmath>
using namespace std;
vector <long long> primes{ 3, 5 };
int main() { cout.imbue(locale("")); const int cutOff = 200, bigUn = 100000, chunks = 50, little = bigUn / chunks;
const char tn[] = " cuban prime";
cout << "The first " << cutOff << tn << "s:" << endl; int c = 0; bool showEach = true; long long u = 0, v = 1; auto st = chrono::system_clock::now();
for (long long i = 1; i <= LLONG_MAX; i++) { bool found = false; long long mx = (long long)(ceil(sqrt(v += (u += 6)))); for (long long item : primes) { if (item > mx) break; if (v % item == 0) { found = true; break; } } if (!found) { c += 1; if (showEach) { for (long long z = primes.back() + 2; z <= v - 2; z += 2) { bool fnd = false; for (long long item : primes) { if (item > mx) break; if (z % item == 0) { fnd = true; break; } } if (!fnd) primes.push_back(z); } primes.push_back(v); cout.width(11); cout << v; if (c % 10 == 0) cout << endl; if (c == cutOff) { showEach = false; cout << "\nProgress to the " << bigUn << "th" << tn << ": "; } } if (c % little == 0) { cout << "."; if (c == bigUn) break; } } } cout << "\nThe " << c << "th" << tn << " is " << v; chrono::duration<double> elapsed_seconds = chrono::system_clock::now() - st; cout << "\nComputation time was " << elapsed_seconds.count() << " seconds" << endl; return 0; }</lang>
- Output:
The first 200 cuban primes: 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 Progress to the 100,000th cuban prime: .................................................. The 100,000th cuban prime is 1,792,617,147,127 Computation time was 35.5644 seconds
C#
(of the Snail Version) <lang csharp>using System; using System.Collections.Generic; using System.Linq;
static class Program {
static List<long> primes = new List<long>() { 3, 5 };
static void Main(string[] args) { const int cutOff = 200; const int bigUn = 100000; const int chunks = 50; const int little = bigUn / chunks; const string tn = " cuban prime"; Console.WriteLine("The first {0:n0}{1}s:", cutOff, tn); int c = 0; bool showEach = true; long u = 0, v = 1; DateTime st = DateTime.Now; for (long i = 1; i <= long.MaxValue; i++) { bool found = false; int mx = System.Convert.ToInt32(Math.Ceiling(Math.Sqrt(v += (u += 6)))); foreach (long item in primes) { if (item > mx) break; if (v % item == 0) { found = true; break; } } if (!found) { c += 1; if (showEach) { for (var z = primes.Last() + 2; z <= v - 2; z += 2) { bool fnd = false; foreach (long item in primes) { if (item > mx) break; if (z % item == 0) { fnd = true; break; } } if (!fnd) primes.Add(z); } primes.Add(v); Console.Write("{0,11:n0}", v); if (c % 10 == 0) Console.WriteLine(); if (c == cutOff) { showEach = false; Console.Write("\nProgress to the {0:n0}th{1}: ", bigUn, tn); } } if (c % little == 0) { Console.Write("."); if (c == bigUn) break; } } } Console.WriteLine("\nThe {1:n0}th{2} is {0,17:n0}", v, c, tn); Console.WriteLine("Computation time was {0} seconds", (DateTime.Now - st).TotalSeconds); if (System.Diagnostics.Debugger.IsAttached) Console.ReadKey(); }
}</lang>
- Output:
The first 200 cuban primes: 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 Progress to the 100,000th cuban prime: .................................................. The 100,000th cuban prime is 1,792,617,147,127 Computation time was 63.578673 seconds
Go
<lang go>package main
import (
"fmt" "math/big"
)
func commatize(n uint64) string {
s := fmt.Sprintf("%d", n) le := len(s) for i := le - 3; i >= 1; i -= 3 { s = s[0:i] + "," + s[i:] } return s
}
func main() {
var z big.Int var cube1, cube2, cube100k, diff uint64 cubans := make([]string, 200) cube1 = 1 count := 0 for i := 1; ; i++ { j := i + 1 cube2 = uint64(j * j * j) diff = cube2 - cube1 z.SetUint64(diff) if z.ProbablyPrime(0) { // 100% accurate for z < 2 ^ 64 if count < 200 { cubans[count] = commatize(diff) } count++ if count == 100000 { cube100k = diff break } } cube1 = cube2 } fmt.Println("The first 200 cuban primes are:-") for i := 0; i < 20; i++ { j := i * 10 fmt.Printf("%9s\n", cubans[j : j+10]) // 10 per line say } fmt.Println("\nThe 100,000th cuban prime is", commatize(cube100k))
}</lang>
- Output:
The first 200 cuban primes are:- [ 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
Pascal
uses trial division to check primility.Slow in such number ranges.
OutNthCubPrime(10000) takes only 0,950 s.
100: 283,669; 1000: 65,524,807; 10000: 11,712,188,419; 100000: 1,792,617,147,127
<lang pascal>program CubanPrimes; {$IFDEF FPC}
{$MODE DELPHI} {$OPTIMIZATION ON,Regvar,PEEPHOLE,CSE,ASMCSE} {$CODEALIGN proc=32}
{$ENDIF} uses
primTrial;
const
COLUMNCOUNT = 10*10;
procedure FormOut(Cuban:Uint64;ColSize:Uint32); var
s : String; pI,pJ :pChar; i,j : NativeInt;
Begin
str(Cuban,s); i := length(s); If i>3 then Begin //extend s by the count of comma to be inserted j := i+ (i-1) div 3; setlength(s,j); pI := @s[i]; pJ := @s[j]; while i > 3 do Begin // copy 3 digits pJ^ := pI^;dec(pJ);dec(pI); pJ^ := pI^;dec(pJ);dec(pI); pJ^ := pI^;dec(pJ);dec(pI); // insert comma pJ^ := ',';dec(pJ); dec(i,3); end; //the digits in front are in the right place end; write(s:ColSize);
end;
procedure OutFirstCntCubPrimes(Cnt : Int32;ColCnt : Int32); var
cbDelta1, cbDelta2 : Uint64; ClCnt,ColSize : NativeInt;
Begin
If Cnt <= 0 then EXIT; IF ColCnt <= 0 then ColCnt := 1; ColSize := COLUMNCOUNT DIV ColCnt; dec(ColCnt);
ClCnt := ColCnt; cbDelta1 := 0; cbDelta2 := 1;
repeat if isPrime(cbDelta2) then Begin FormOut(cbDelta2,ColSize); dec(Cnt);
dec(ClCnt); If ClCnt < 0 then Begin Writeln; ClCnt := ColCnt; end; end; inc(cbDelta1,6);// 0,6,12,18... inc(cbDelta2,cbDelta1);//1,7,19,35... until Cnt<= 0;
writeln;
end;
procedure OutNthCubPrime(n : Int32); var
cbDelta1, cbDelta2 : Uint64;
Begin
If n <= 0 then EXIT; cbDelta1 := 0; cbDelta2 := 1;
repeat inc(cbDelta1,6); inc(cbDelta2,cbDelta1); if isPrime(cbDelta2) then dec(n); until n<=0;
FormOut(cbDelta2,20); writeln;
end;
Begin
OutFirstCntCubPrimes(200,10); OutNthCubPrime(100000);
end.</lang>
- Output:
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 1,792,617,147,127 //user 2m1.950s
Perl
<lang perl>use feature 'say'; use ntheory 'is_prime';
sub cuban_primes {
my ($n) = @_;
my @primes; for (my $k = 1 ; ; ++$k) { my $p = 3 * $k * ($k + 1) + 1; if (is_prime($p)) { push @primes, $p; last if @primes >= $n; } }
return @primes;
}
sub commify {
join ',', reverse map { scalar reverse } unpack "(A3)*", reverse shift;
}
my @c = cuban_primes(200);
while (@c) {
say join ' ', map { sprintf "%9s", commify $_ } splice(@c, 0, 10);
}
say ; for my $n (1 .. 6) {
say "10^$n-th cuban prime is: ", commify((cuban_primes(10**$n))[-1]);
}</lang>
- Output:
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 10^1-th cuban prime is: 631 10^2-th cuban prime is: 283,669 10^3-th cuban prime is: 65,524,807 10^4-th cuban prime is: 11,712,188,419 10^5-th cuban prime is: 1,792,617,147,127 10^6-th cuban prime is: 255,155,578,239,277
Perl 6
Not the most efficient, but concise, and good enough for this task. <lang perl6>sub comma { $^i.flip.comb(3).join(',').flip }
my @cubans = lazy (1..Inf).hyper(:8degree).map({ ($_+1)³ - .³ }).grep: *.is-prime;
put @cubans[^200]».&comma».fmt("%9s").rotor(10).join: "\n";
put ;
put @cubans[99_999]., # zero indexed</lang>
- Output:
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 1,792,617,147,127
After reading up a bit, the general form for cuban primes is prime numbers of the form ((x+k)3 - x3)/k where k mod 3 is not equal 0.
The cubans where k == 1 (the focus of this task) is one of many possible groups. In general, it seems like the cubans where k == 1 and k==2 are the two primary cases, but it is possible to have cubans with a k of any integer that is not a multiple of 3.
Here are the first 20 for each valid k up to 10: <lang perl6>sub comma { $^i.flip.comb(3).join(',').flip }
for 2..10 -> \k {
next if k %% 3; my @cubans = lazy (1..Inf).hyper(:8degree).map({ (($_+k)³ - .³)/k }).grep: *.is-prime; put "First 20 cuban primes where k = {k}:"; put @cubans[^20]».&comma».fmt("%7s").rotor(10).join: "\n"; put ;
} </lang>
- Output:
First 20 cuban primes where k = 2: 13 109 193 433 769 1,201 1,453 2,029 3,469 3,889 4,801 10,093 12,289 13,873 18,253 20,173 21,169 22,189 28,813 37,633 First 20 cuban primes where k = 4: 31 79 151 367 1,087 1,327 1,879 2,887 3,271 4,111 4,567 6,079 7,207 8,431 15,991 16,879 17,791 19,687 23,767 24,847 First 20 cuban primes where k = 5: 43 67 97 223 277 337 727 823 1,033 1,663 2,113 2,617 2,797 3,373 4,003 5,683 6,217 7,963 10,273 10,627 First 20 cuban primes where k = 7: 73 103 139 181 229 283 409 643 733 829 1,039 1,153 1,399 1,531 1,669 2,281 2,803 3,181 3,583 3,793 First 20 cuban primes where k = 8: 163 379 523 691 883 2,203 2,539 3,691 5,059 5,563 6,091 7,219 8,443 9,091 10,459 11,923 15,139 19,699 24,859 27,091 First 20 cuban primes where k = 10: 457 613 997 1,753 2,053 2,377 4,357 6,373 9,433 13,093 16,453 21,193 27,673 28,837 31,237 37,657 46,153 47,653 49,177 62,233
REXX
<lang rexx>/*REXX program finds and displays a number of cuban primes or the Nth cuban prime. */ numeric digits 20 /*ensure enought decimal digits for #s.*/ parse arg N . /*obtain optional argument from the CL.*/ if N== | N=="," then N= 200 /*Not specified? Then use the default.*/ Nth= N<0 /*used for finding the Nth cuban prime.*/
- = 0 /*number of cuban primes found so far. */
!.=0; !.0=1; !.2=1; !.3=1; !.4=1; !.5=1; !.6=1; !.8=1; s=41; $= sw= linesize() - 1; if sw<1 then sw=79 /*obtain width of the terminal screen. */ if (Nth & N==1) | N>0 then $= 7 /*handle case of the 1st cuban prime.*/ if (Nth & N==2) | N>1 then $= $ 19 /* " " " " 2nd " " */ if (Nth & N==3) | N>2 then $= $ 37 /* " " " " 3rd " " */
- = 3 /*above are needed for prime generation*/
N= abs(N) /*use absolute value of N from now on*/ if #<N then /* [↑] ending digs that aren't cubans.*/
do j=4 until #=>N; x= (j+1)**3 - j**3 /*compute a possible cuban*/ parse var x -1 _; if !._ then iterate /*check for the last digit*/ if x// 3==0 then iterate; if x// 7==0 then iterate /* " " ÷ 3; for ÷ 7 */ if x//11==0 then iterate; if x//13==0 then iterate /* " " ÷11; " ÷ 13 */ if x//17==0 then iterate; if x//19==0 then iterate /* " " ÷17; " ÷ 19 */ if x//23==0 then iterate; if x//29==0 then iterate /* " " ÷23; " ÷ 29 */ if x//31==0 then iterate; if x//37==0 then iterate /* " " ÷31; " ÷ 37 */
do k=s by 6 until k*k>x /*skip multiples of 3 (when using BY 6)*/ if x// k ==0 then iterate j /*test for a "lower" possible prime. */ if x//(k+2) ==0 then iterate j /* " " " "higher" " " */ end /*k*/ #= # + 1 /*bump the number of cuban primes found*/ if Nth then do; if #==N then do; say commas(x); leave j; end /*display 1 num*/ else iterate j /*keep searching. */ end new=$ commas(x) /*append a new cuban. */ if length(new)>sw then do; say $ /*line too long, show #s*/ $= commas(x) /*initialize next line. */ end else $= new /*use this longer output*/ end /*j*/
if S\== then say $ /*check for any residual*/ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _</lang>
- output when using the default input of: 200
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
- output when using the input of: -100000
1,792,617,147,127
Sidef
<lang ruby>func cuban_primes(n) {
1..Inf -> lazy.map {|k| 3*k*(k+1) + 1 }\ .grep{ .is_prime }\ .first(n)
}
cuban_primes(200).slices(10).each {
say .map { "%9s" % .commify }.join(' ')
}
say ("\n100,000th cuban prime is: ", cuban_primes(1e5).last.commify)</lang>
- Output:
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 100,000th cuban prime is: 1,792,617,147,127
Visual Basic .NET
Corner Cutting Version
This language doesn't have a built-in for a IsPrime() function, so I was surprised to find that this runs so quickly. It builds a list of primes while it is creating the output table. Since the last item on the table is larger than the square root of the 100,000th cuban prime, there is no need to continue adding to the prime list while checking up to the 100,000th cuban prime. I found a bit of a shortcut, if you skip the iterator by just the right amount, only one value is tested for the final result. It's hard-coded in the program, so if another final cuban prime were to be selected for output, the program would need a re-write. If not skipping ahead to the answer, it takes a few seconds over a minute to eventually get to it (see Snail Version below). <lang vbnet>Module Module1
Dim primes As List(Of Long) = {3L, 5L}.ToList()
Sub Main(args As String()) Const cutOff As Integer = 200, bigUn As Integer = 100000, tn As String = " cuban prime" Console.WriteLine("The first {0:n0}{1}s:", cutOff, tn) Dim c As Integer = 0, showEach As Boolean = True, skip As Boolean = True, v As Long = 0, st As DateTime = DateTime.Now For i As Long = 1 To Long.MaxValue v = 3 * i : v = v * i + v + 1 Dim found As Boolean = False, mx As Integer = Math.Ceiling(Math.Sqrt(v)) For Each item In primes If item > mx Then Exit For If v Mod item = 0 Then found = True : Exit For Next : If Not found Then c += 1 : If showEach Then For z = primes.Last + 2 To v - 2 Step 2 Dim fnd As Boolean = False For Each item In primes If item > mx Then Exit For If z Mod item = 0 Then fnd = True : Exit For Next : If Not fnd Then primes.Add(z) Next : primes.Add(v) : Console.Write("{0,11:n0}", v) If c Mod 10 = 0 Then Console.WriteLine() If c = cutOff Then showEach = False Else If skip Then skip = False : i += 772279 : c = bigUn - 1 End If If c = bigUn Then Exit For End If Next Console.WriteLine("{1}The {2:n0}th{3} is {0,17:n0}", v, vbLf, c, tn) Console.WriteLine("Computation time was {0} seconds", (DateTime.Now - st).TotalSeconds) If System.Diagnostics.Debugger.IsAttached Then Console.ReadKey() End Sub
End Module</lang>
- Output:
The first 200 cuban primes: 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 Computation time was 0.2989494 seconds
Snail Version
This one doesn't take any shortcuts. It could be sped up (Execution time about 15 seconds) by threading chunks of the search for the 100,000th cuban prime, but you would have to take a guess about how far to go, which would be hard-coded, so one might as well use the short-cut version if you are willing to overlook that difficulty. <lang vbnet>'Imports System.Threading.Tasks
'Module Program
' Dim primes As New List(Of Long) ' Dim ic As Long = 0
' Function tabulate(i As Long, amt As Integer) As Integer ' tabulate = 0 ' For j As Long = i To i + amt - 1 ' Dim v As Long = 3 * j : v = v * j + v + 1 ' Dim found As Boolean = False, mx As Integer = Math.Ceiling(Math.Sqrt(v)) ' For Each item In primes ' If item > mx Then Exit For ' If v Mod item = 0 Then found = True : Exit For ' Next : If Not found Then tabulate += 1 ' Next : Console.Write(".") ' End Function
' Sub Main(args As String()) ' Dim taskList As New List(Of Task(Of Integer)) ' Const cutOff As Integer = 200, bigUn As Integer = 100000, ' chunks As Integer = 50 ' Console.WriteLine("The first {0:n0} Cuban primes:", cutOff) ' primes.Add(3) : primes.Add(5) ' Dim c As Integer = 0, showEach As Boolean = True, para As Boolean = True ' Dim v As Long = 0 ' Dim st As DateTime = DateTime.Now ' For i As Long = 1 To Long.MaxValue ' v = 3 * i : v = v * i + v + 1 ' Dim found As Boolean = False, mx As Integer = Math.Ceiling(Math.Sqrt(v)) ' For Each item In primes ' If item > mx Then Exit For ' If v Mod item = 0 Then found = True : Exit For ' Next : If Not found Then ' c += 1 : If showEach Then ' For z = primes.Last + 2 To v - 2 Step 2 ' Dim fnd As Boolean = False ' For Each item In primes ' If item > mx Then Exit For ' If z Mod item = 0 Then fnd = True : Exit For ' Next : If Not fnd Then primes.Add(z) ' Next : primes.Add(v) : Console.Write("{0,11:n0}", v) ' If c Mod 10 = 0 Then Console.WriteLine() ' If c = cutOff Then showEach = False : _ ' Console.Write("{0}Progress to the {1:n0}th Cuban prime: ", vbLf, bigUn) ' Else ' If para Then ' Const shortCutDistance As Integer = 770000 ' Dim amt As Integer = shortCutDistance / chunks ' For ii As Integer = 0 To shortCutDistance - 1 Step amt ' Dim ti As Integer = If(ii = 0, i + 1, ii), ' ta As Integer = If(ii = 0, amt - i - 1, amt) ' taskList.Add(Task.Run(Function() tabulate(ti, ta))) ' Next ' Task.WhenAll(taskList) ' For Each item In taskList.Select(Function(t) t.Result) ' c += item : Next ' para = False : i = shortCutDistance - 1 ' End If ' End If ' If c = bigUn Then Exit For ' End If ' Next ' Console.WriteLine("{1}The {2:n0}th Cuban prime is {0,17:n0}", v, vbLf, c) ' Console.WriteLine("Computation time was {0} seconds", (DateTime.Now - st).TotalSeconds) ' If System.Diagnostics.Debugger.IsAttached Then Console.ReadKey() ' End Sub
'End Module
Module Program
Dim primes As List(Of Long) = {3L, 5L}.ToList()
Sub Main(args As String()) Dim taskList As New List(Of Task(Of Integer)) Const cutOff As Integer = 200, bigUn As Integer = 100000, chunks As Integer = 50, little As Integer = bigUn / chunks, tn As String = " cuban prime" Console.WriteLine("The first {0:n0}{1}s:", cutOff, tn) Dim c As Integer = 0, showEach As Boolean = True, u As Long = 0, v As Long = 1, st As DateTime = DateTime.Now For i As Long = 1 To Long.MaxValue u += 6 : v += u Dim found As Boolean = False, mx As Integer = Math.Ceiling(Math.Sqrt(v)) For Each item In primes If item > mx Then Exit For If v Mod item = 0 Then found = True : Exit For Next : If Not found Then c += 1 : If showEach Then For z = primes.Last + 2 To v - 2 Step 2 Dim fnd As Boolean = False For Each item In primes If item > mx Then Exit For If z Mod item = 0 Then fnd = True : Exit For Next : If Not fnd Then primes.Add(z) Next : primes.Add(v) : Console.Write("{0,11:n0}", v) If c Mod 10 = 0 Then Console.WriteLine() If c = cutOff Then showEach = False : _ Console.Write("{0}Progress to the {1:n0}th{2}: ", vbLf, bigUn, tn) End If If c Mod little = 0 Then Console.Write(".") : If c = bigUn Then Exit For End If Next Console.WriteLine("{1}The {2:n0}th{3} is {0,17:n0}", v, vbLf, c, tn) Console.WriteLine("Computation time was {0} seconds", (DateTime.Now - st).TotalSeconds) If System.Diagnostics.Debugger.IsAttached Then Console.ReadKey() End Sub
End Module</lang>
- Output:
The first 200 cuban primes: 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 Progress to the 100,000th cuban prime: .................................................. The 100,000th cuban prime is 1,792,617,147,127 Computation time was 49.5868152 seconds