Posted on by Kalkicode
Code Number

Cuban prime numbers

The given problem is about finding and identifying Cuban prime numbers within a specific range. Cuban primes are a subset of prime numbers and are defined by the formula 3n^2 + 3n + 1, where n is a non-negative integer. The goal is to generate and identify Cuban primes up to a given limit.

Problem Statement

The task is to implement a program that can efficiently calculate and identify Cuban prime numbers. The program should be able to find the nth Cuban prime and print a list of Cuban primes within a given range.

Explanation with Example

Let's take a simple example to understand the concept of Cuban primes. Let's find the first 10 Cuban primes:

1. For n = 0, 30^2 + 30 + 1 = 1 (which is not a prime).
2. For n = 1, 31^2 + 31 + 1 = 7 (which is a Cuban prime).
3. For n = 2, 32^2 + 32 + 1 = 19 (which is a Cuban prime).
4. For n = 3, 33^2 + 33 + 1 = 37 (which is a Cuban prime).
5. For n = 4, 34^2 + 34 + 1 = 61 (which is a Cuban prime).
6. For n = 5, 35^2 + 35 + 1 = 91 (which is not a prime).
7. For n = 6, 36^2 + 36 + 1 = 127 (which is a Cuban prime).
8. For n = 7, 37^2 + 37 + 1 = 169 (which is not a prime).
9. For n = 8, 38^2 + 38 + 1 = 217 (which is not a prime).
10. For n = 9, 39^2 + 39 + 1 = 271 (which is a Cuban prime).

So, the first 10 Cuban primes are: 7, 19, 37, 61, 127, 271, 331, 397, 547, 631.

Pseudocode and Algorithm

``````// Function to pre-calculate prime numbers using Sieve of Eratosthenes algorithm
function calculatePrime():
limit := 1000000
primes[0..limit] := true

for i from 2 to limit:
primes[i] := true

for i from 2 to limit:
if primes[i] is true:
for j from 2*i to limit with step i:
primes[j] := false

// Function to check if a number is a Cuban prime
function isCubanPrime(num):
if num <= 0:
return false

if num < limit:
return primes[num]

max := integer part of square root of num

for i from 3 to max with step 1:
if primes[i] is true and num % i == 0:
return false

return true

// Function to find the nth Cuban prime
function nthCubanPrime(n):
count := 0
result := 0
num := 0

for i from 0 to infinity:
num := 1 + 3 * i * (i + 1)
if isCubanPrime(num) is true:
count := count + 1
result := num
if count == n:
break

return result

// Function to print first n Cuban primes
function printCubanPrime(n):
count := 0

for i from 0 to infinity:
num := 1 + 3 * i * (i + 1)
if isCubanPrime(num) is true:
count := count + 1
print num
if count == n:
break

// Main function
function main():
calculatePrime()

// Test A
print "Cuban prime numbers from 1 to 100 are:"
printCubanPrime(100)

// Test B
print "67-th Cuban prime is:", nthCubanPrime(67)
print "154-th Cuban prime is:", nthCubanPrime(154)``````

The given Java code provides an efficient solution to find Cuban primes. Here's a high-level explanation of the algorithm:

1. Initialize a boolean array called 'primes' of size 'limit' (1 million in this case) to store whether a number is prime or not.
2. Implement the 'calculatePrime' method to pre-calculate prime numbers using the Sieve of Eratosthenes algorithm.
3. Implement the 'isCubanPrime' method to check if a number is a Cuban prime. If the number is within the pre-calculated prime limit, it checks directly from the array. Otherwise, it iterates from 3 up to the square root of the number to validate its primality.
4. Implement the 'nthCubanPrime' method to find the nth Cuban prime by iterating through numbers generated by the formula 3n^2 + 3n + 1 and checking their primality with the 'isCubanPrime' method.
5. Implement the 'printCubanPrime' method to print a given number of Cuban primes within a range.

Code Solution

Here given code implementation process.

``````// Java program for
// Cuban prime numbers
public class CubanPrimes
{
public int limit;
public boolean[] primes;
public CubanPrimes()
{
// This is prime number limit
this.limit = 1000000;
this.primes = new boolean[this.limit];
this.calculatePrime();
}
// Pre calculate prime  number under limit
public void calculatePrime()
{
//  Set initial all element is prime
for (int i = 2; i < this.limit; i++)
{
this.primes[i] = true;
}
for (int i = 2; i < this.limit; ++i)
{
if (this.primes[i] == true)
{
for (int j = 2 *i; j < this.limit; j += i)
{
this.primes[j] = false;
}
}
}
}
public boolean isCubanPrime(long num)
{
if (num <= 0)
{
return false;
}
if (num < limit)
{
// When number is under exist limit
return primes[(int) num];
}
// In case number is more than limit.
// Get square root of number
int max = (int) Math.sqrt(num);
// Check that number is cuban primes or not
for (int i = 3; i <= max; ++i)
{
if (primes[i] && (num % i) == 0)
{
return false;
}
}
// When number is cuban prime
return true;
}
public void nthCubanPrime(int n)
{
int count = 0;
long result = 0;
long num = 0;
for (long i = 0; count < n; ++i)
{
num = 1l + 3 *i *(i + 1);
if (this.isCubanPrime(num))
{
result = num;
count++;
}
}
System.out.print("\n " + n + "-th cuban prime is " + result);
}
public void printCubanPrime(int n)
{
if (n <= 0)
{
return;
}
System.out.print("\n  Cuban prime numbers from 1 to " + n + " is \n");
int count = 0;
for (long i = 0; count < n; i++)
{
long num = 1l + 3 *i *(i + 1);
if (this.isCubanPrime(num))
{
count++;
System.out.print("\t" + num);
if (count % 5 == 0)
{
System.out.print("\n");
}
}
}
}
public static void main(String[] args)
{
// Test A
// Print initial 100 cuban prime number
// Test B
}
}``````

Output

``````  Cuban prime numbers from 1 to 100 is
7	19	37	61	127
271	331	397	547	631
919	1657	1801	1951	2269
2437	2791	3169	3571	4219
4447	5167	5419	6211	7057
7351	8269	9241	10267	11719
12097	13267	13669	16651	19441
19927	22447	23497	24571	25117
26227	27361	33391	35317	42841
45757	47251	49537	50311	55897
59221	60919	65269	70687	73477
74419	75367	81181	82171	87211
88237	89269	92401	96661	102121
103231	104347	110017	112327	114661
115837	126691	129169	131671	135469
140617	144541	145861	151201	155269
163567	169219	170647	176419	180811
189757	200467	202021	213067	231019
234361	241117	246247	251431	260191
263737	267307	276337	279991	283669

67-th cuban prime is 104347
154-th cuban prime is 812761``````
``````// Include header file
#include <iostream>
#include <math.h>

using namespace std;
// C++ program for
// Cuban prime numbers
class CubanPrimes
{
public: int limit;
bool *primes;
CubanPrimes()
{
this->limit = 1000000;
this->primes = new bool[this->limit];
this->calculatePrime();
}
// Pre calculate prime  number under limit
void calculatePrime()
{
//  Set initial all element is prime
for (int i = 2; i < this->limit; i++)
{
this->primes[i] = true;
}
for (int i = 2; i < this->limit; ++i)
{
if (this->primes[i] == true)
{
for (int j = 2 *i; j < this->limit; j += i)
{
this->primes[j] = false;
}
}
}
}
bool isCubanPrime(long num)
{
if (num <= 0)
{
return false;
}
if (num < this->limit)
{
// When number is under exist limit
return this->primes[(int) num];
}
// In case number is more than limit.
// Get square root of number
int max = (int) sqrt(num);
// Check that number is cuban primes or not
for (int i = 3; i <= max; ++i)
{
if (this->primes[i] && (num % i) == 0)
{
return false;
}
}
// When number is cuban prime
return true;
}
void nthCubanPrime(int n)
{
int count = 0;
long result = 0;
long num = 0;
for (long i = 0; count < n; ++i)
{
num = 1L + 3 *i *(i + 1);
if (this->isCubanPrime(num))
{
result = num;
count++;
}
}
cout << "\n " << n << "-th cuban prime is " << result;
}
void printCubanPrime(int n)
{
if (n <= 0)
{
return;
}
cout << "\n  Cuban prime numbers from 1 to " << n << " is \n";
int count = 0;
for (long i = 0; count < n; i++)
{
long num = 1L + 3 *i *(i + 1);
if (this->isCubanPrime(num))
{
count++;
cout << "\t" << num;
if (count % 5 == 0)
{
cout << "\n";
}
}
}
}
};
int main()
{
// Test A
// Print initial 100 cuban prime number
// Test B
return 0;
}``````

Output

``````  Cuban prime numbers from 1 to 100 is
7	19	37	61	127
271	331	397	547	631
919	1657	1801	1951	2269
2437	2791	3169	3571	4219
4447	5167	5419	6211	7057
7351	8269	9241	10267	11719
12097	13267	13669	16651	19441
19927	22447	23497	24571	25117
26227	27361	33391	35317	42841
45757	47251	49537	50311	55897
59221	60919	65269	70687	73477
74419	75367	81181	82171	87211
88237	89269	92401	96661	102121
103231	104347	110017	112327	114661
115837	126691	129169	131671	135469
140617	144541	145861	151201	155269
163567	169219	170647	176419	180811
189757	200467	202021	213067	231019
234361	241117	246247	251431	260191
263737	267307	276337	279991	283669

67-th cuban prime is 104347
154-th cuban prime is 812761``````
``````// Include namespace system
using System;
// Csharp program for
// Cuban prime numbers
public class CubanPrimes
{
public int limit;
public Boolean[] primes;
public CubanPrimes()
{
// This is prime number limit
this.limit = 1000000;
this.primes = new Boolean[this.limit];
this.calculatePrime();
}
// Pre calculate prime  number under limit
public void calculatePrime()
{
//  Set initial all element is prime
for (int i = 2; i < this.limit; i++)
{
this.primes[i] = true;
}
for (int i = 2; i < this.limit; ++i)
{
if (this.primes[i] == true)
{
for (int j = 2 * i; j < this.limit; j += i)
{
this.primes[j] = false;
}
}
}
}
public Boolean isCubanPrime(long num)
{
if (num <= 0)
{
return false;
}
if (num < this.limit)
{
// When number is under exist limit
return this.primes[(int) num];
}
// In case number is more than limit.
// Get square root of number
int max = (int) Math.Sqrt(num);
// Check that number is cuban primes or not
for (int i = 3; i <= max; ++i)
{
if (this.primes[i] && (num % i) == 0)
{
return false;
}
}
// When number is cuban prime
return true;
}
public void nthCubanPrime(int n)
{
int count = 0;
long result = 0;
long num = 0;
for (long i = 0; count < n; ++i)
{
num = 1L + 3 * i * (i + 1);
if (this.isCubanPrime(num))
{
result = num;
count++;
}
}
Console.Write("\n " + n + "-th cuban prime is " + result);
}
public void printCubanPrime(int n)
{
if (n <= 0)
{
return;
}
Console.Write("\n  Cuban prime numbers from 1 to " + n + " is \n");
int count = 0;
for (long i = 0; count < n; i++)
{
long num = 1L + 3 * i * (i + 1);
if (this.isCubanPrime(num))
{
count++;
Console.Write("\t" + num);
if (count % 5 == 0)
{
Console.Write("\n");
}
}
}
}
public static void Main(String[] args)
{
// Test A
// Print initial 100 cuban prime number
// Test B
}
}``````

Output

``````  Cuban prime numbers from 1 to 100 is
7	19	37	61	127
271	331	397	547	631
919	1657	1801	1951	2269
2437	2791	3169	3571	4219
4447	5167	5419	6211	7057
7351	8269	9241	10267	11719
12097	13267	13669	16651	19441
19927	22447	23497	24571	25117
26227	27361	33391	35317	42841
45757	47251	49537	50311	55897
59221	60919	65269	70687	73477
74419	75367	81181	82171	87211
88237	89269	92401	96661	102121
103231	104347	110017	112327	114661
115837	126691	129169	131671	135469
140617	144541	145861	151201	155269
163567	169219	170647	176419	180811
189757	200467	202021	213067	231019
234361	241117	246247	251431	260191
263737	267307	276337	279991	283669

67-th cuban prime is 104347
154-th cuban prime is 812761``````
``````package main
import "math"
import "fmt"
// Go program for
// Cuban prime numbers
type CubanPrimes struct {
limit int
primes []bool
}
func getCubanPrimes() * CubanPrimes {
var me *CubanPrimes = &CubanPrimes {}
// This is prime number limit
me.limit = 1000000
me.primes = make([] bool, me.limit)
me.calculatePrime()
return me
}
// Pre calculate prime  number under limit
func(this CubanPrimes) calculatePrime() {
//  Set initial all element is prime
for i := 2 ; i < this.limit ; i++ {
this.primes[i] = true
}
for i := 2 ; i < this.limit ; i++ {
if this.primes[i] == true {
for j := 2 * i ; j < this.limit ; j += i {
this.primes[j] = false
}
}
}
}
func(this CubanPrimes) isCubanPrime(num int) bool {
if num <= 0 {
return false
}
if num < this.limit {
// When number is under exist limit
return this.primes[num]
}
// In case number is more than limit.
// Get square root of number
var max int = int(math.Sqrt(float64(num)))
// Check that number is cuban primes or not
for i := 3 ; i <= max ; i++ {
if this.primes[i] && (num % i) == 0 {
return false
}
}
// When number is cuban prime
return true
}
func(this CubanPrimes) nthCubanPrime(n int) {
var count int = 0
var result int = 0
var num int = 0
for i := 0 ; count < n ; i++ {
num = 1 + 3 * i * (i + 1)
if this.isCubanPrime(num) {
result = num
count++
}
}
fmt.Print("\n ", n, "-th cuban prime is ", result)
}
func(this CubanPrimes) printCubanPrime(n int) {
if n <= 0 {
return
}
fmt.Print("\n  Cuban prime numbers from 1 to ", n, " is \n")
var count int = 0
for i := 0 ; count < n ; i++ {
var num int = 1 + 3 * i * (i + 1)
if this.isCubanPrime(num) {
count++
fmt.Print("\t", num)
if count % 5 == 0 {
fmt.Print("\n")
}
}
}
}
func main() {
var task * CubanPrimes = getCubanPrimes()
// Test A
// Print initial 100 cuban prime number
// Test B
}``````

Output

``````  Cuban prime numbers from 1 to 100 is
7	19	37	61	127
271	331	397	547	631
919	1657	1801	1951	2269
2437	2791	3169	3571	4219
4447	5167	5419	6211	7057
7351	8269	9241	10267	11719
12097	13267	13669	16651	19441
19927	22447	23497	24571	25117
26227	27361	33391	35317	42841
45757	47251	49537	50311	55897
59221	60919	65269	70687	73477
74419	75367	81181	82171	87211
88237	89269	92401	96661	102121
103231	104347	110017	112327	114661
115837	126691	129169	131671	135469
140617	144541	145861	151201	155269
163567	169219	170647	176419	180811
189757	200467	202021	213067	231019
234361	241117	246247	251431	260191
263737	267307	276337	279991	283669

67-th cuban prime is 104347
154-th cuban prime is 812761``````
``````<?php
// Php program for
// Cuban prime numbers
class CubanPrimes
{
public \$limit;
public \$primes;

public	function __construct()
{
\$this->limit = 100000;
\$this->primes = array_fill(0, \$this->limit, false);
\$this->calculatePrime();
}
// Pre calculate prime  number under limit
public	function calculatePrime()
{
//  Set initial all element is prime
for (\$i = 2; \$i < \$this->limit; \$i++)
{
\$this->primes[\$i] = true;
}
for (\$i = 2; \$i < \$this->limit; ++\$i)
{
if (\$this->primes[\$i] == true)
{
for (\$j = 2 * \$i; \$j < \$this->limit; \$j += \$i)
{
\$this->primes[\$j] = false;
}
}
}
}
public	function isCubanPrime(\$num)
{
if (\$num <= 0)
{
return false;
}
if (\$num < \$this->limit)
{
// When number is under exist limit
return \$this->primes[(int) \$num];
}
// In case number is more than limit.
// Get square root of number
\$max = (int) sqrt(\$num);
// Check that number is cuban primes or not
for (\$i = 3; \$i <= \$max; ++\$i)
{
if (\$this->primes[\$i] && (\$num % \$i) == 0)
{
return false;
}
}
// When number is cuban prime
return true;
}
public	function nthCubanPrime(\$n)
{
\$count = 0;
\$result = 0;
\$num = 0;
for (\$i = 0; \$count < \$n; ++\$i)
{
\$num = 1 + 3 * \$i * (\$i + 1);
if (\$this->isCubanPrime(\$num))
{
\$result = \$num;
\$count++;
}
}
echo("\n ".\$n.
"-th cuban prime is ".\$result);
}
public	function printCubanPrime(\$n)
{
if (\$n <= 0)
{
return;
}
echo("\n  Cuban prime numbers from 1 to ".\$n.
" is \n");
\$count = 0;
for (\$i = 0; \$count < \$n; \$i++)
{
\$num = 1 + 3 * \$i * (\$i + 1);
if (\$this->isCubanPrime(\$num))
{
\$count++;
echo("\t".\$num);
if (\$count % 5 == 0)
{
echo("\n");
}
}
}
}
}

function main()
{
// Test A
// Print initial 100 cuban prime number
// Test B
}
main();``````

Output

``````  Cuban prime numbers from 1 to 100 is
7	19	37	61	127
271	331	397	547	631
919	1657	1801	1951	2269
2437	2791	3169	3571	4219
4447	5167	5419	6211	7057
7351	8269	9241	10267	11719
12097	13267	13669	16651	19441
19927	22447	23497	24571	25117
26227	27361	33391	35317	42841
45757	47251	49537	50311	55897
59221	60919	65269	70687	73477
74419	75367	81181	82171	87211
88237	89269	92401	96661	102121
103231	104347	110017	112327	114661
115837	126691	129169	131671	135469
140617	144541	145861	151201	155269
163567	169219	170647	176419	180811
189757	200467	202021	213067	231019
234361	241117	246247	251431	260191
263737	267307	276337	279991	283669

67-th cuban prime is 104347
154-th cuban prime is 812761``````
``````// Node JS program for
// Cuban prime numbers
class CubanPrimes
{

constructor()
{
this.limit = 1000000;
this.primes = Array(this.limit).fill(false);
this.calculatePrime();
}
// Pre calculate prime  number under limit
calculatePrime()
{
//  Set initial all element is prime
for (var i = 2; i < this.limit; i++)
{
this.primes[i] = true;
}
for (var i = 2; i < this.limit; ++i)
{
if (this.primes[i] == true)
{
for (var j = 2 * i; j < this.limit; j += i)
{
this.primes[j] = false;
}
}
}
}
isCubanPrime(num)
{
if (num <= 0)
{
return false;
}
if (num < this.limit)
{
// When number is under exist limit
return this.primes[num];
}
// In case number is more than limit.
// Get square root of number
var max = math.sqrt(num);
// Check that number is cuban primes or not
for (var i = 3; i <= max; ++i)
{
if (this.primes[i] && (num % i) == 0)
{
return false;
}
}
// When number is cuban prime
return true;
}
nthCubanPrime(n)
{
var count = 0;
var result = 0;
var num = 0;
for (var i = 0; count < n; ++i)
{
num = 1 + 3 * i * (i + 1);
if (this.isCubanPrime(num))
{
result = num;
count++;
}
}
process.stdout.write("\n " + n + "-th cuban prime is " + result);
}
printCubanPrime(n)
{
if (n <= 0)
{
return;
}
process.stdout.write("\n  Cuban prime numbers from 1 to " + n + " is \n");
var count = 0;
for (var i = 0; count < n; i++)
{
var num = 1 + 3 * i * (i + 1);
if (this.isCubanPrime(num))
{
count++;
process.stdout.write("\t" + num);
if (count % 5 == 0)
{
process.stdout.write("\n");
}
}
}
}
}

function main()
{
// Test A
// Print initial 100 cuban prime number
// Test B
}
main();``````

Output

``````  Cuban prime numbers from 1 to 100 is
7	19	37	61	127
271	331	397	547	631
919	1657	1801	1951	2269
2437	2791	3169	3571	4219
4447	5167	5419	6211	7057
7351	8269	9241	10267	11719
12097	13267	13669	16651	19441
19927	22447	23497	24571	25117
26227	27361	33391	35317	42841
45757	47251	49537	50311	55897
59221	60919	65269	70687	73477
74419	75367	81181	82171	87211
88237	89269	92401	96661	102121
103231	104347	110017	112327	114661
115837	126691	129169	131671	135469
140617	144541	145861	151201	155269
163567	169219	170647	176419	180811
189757	200467	202021	213067	231019
234361	241117	246247	251431	260191
263737	267307	276337	279991	283669

67-th cuban prime is 104347
154-th cuban prime is 812761``````
``````import math
#  Python 3 program for
#  Cuban prime numbers
class CubanPrimes :

def __init__(self) :
self.limit = 1000000
self.primes = [False] * (self.limit)
self.calculatePrime()

#  Pre calculate prime  number under limit
def calculatePrime(self) :
i = 2
#   Set initial all element is prime
while (i < self.limit) :
self.primes[i] = True
i += 1

i = 2
while (i < self.limit) :
if (self.primes[i] == True) :
j = 2 * i
while (j < self.limit) :
self.primes[j] = False
j += i

i += 1

def isCubanPrime(self, num) :
if (num <= 0) :
return False

if (num < self.limit) :
#  When number is under exist limit
return self.primes[ num]

#  In case number is more than limit.
#  Get square root of number
max =  math.sqrt(num)
i = 3
#  Check that number is cuban primes or not
while (i <= max) :
if (self.primes[i] and(num % i) == 0) :
return False

i += 1

#  When number is cuban prime
return True

def nthCubanPrime(self, n) :
count = 0
result = 0
num = 0
i = 0
while (count < n) :
num = 1 + 3 * i * (i + 1)
if (self.isCubanPrime(num)) :
result = num
count += 1

i += 1

print("\n ", n ,"-th cuban prime is ", result, end = "")

def printCubanPrime(self, n) :
if (n <= 0) :
return

print("\n  Cuban prime numbers from 1 to ", n ," is ")
count = 0
i = 0
while (count < n) :
num = 1 + 3 * i * (i + 1)
if (self.isCubanPrime(num)) :
count += 1
print("\t", num, end = "")
if (count % 5 == 0) :
print(end = "\n")

i += 1

def main() :
#  Test A
#  Print initial 100 cuban prime number
#  Test B

if __name__ == "__main__": main()``````

Output

``````  Cuban prime numbers from 1 to  100  is
7	 19	 37	 61	 127
271	 331	 397	 547	 631
919	 1657	 1801	 1951	 2269
2437	 2791	 3169	 3571	 4219
4447	 5167	 5419	 6211	 7057
7351	 8269	 9241	 10267	 11719
12097	 13267	 13669	 16651	 19441
19927	 22447	 23497	 24571	 25117
26227	 27361	 33391	 35317	 42841
45757	 47251	 49537	 50311	 55897
59221	 60919	 65269	 70687	 73477
74419	 75367	 81181	 82171	 87211
88237	 89269	 92401	 96661	 102121
103231	 104347	 110017	 112327	 114661
115837	 126691	 129169	 131671	 135469
140617	 144541	 145861	 151201	 155269
163567	 169219	 170647	 176419	 180811
189757	 200467	 202021	 213067	 231019
234361	 241117	 246247	 251431	 260191
263737	 267307	 276337	 279991	 283669

67 -th cuban prime is  104347
154 -th cuban prime is  812761``````
``````#  Ruby program for
#  Cuban prime numbers
class CubanPrimes
# Define the accessor and reader of class CubanPrimes
attr_accessor :limit, :primes
def initialize()
self.limit = 1000000
self.primes = Array.new(self.limit) {false}
self.calculatePrime()
end

#  Pre calculate prime  number under limit
def calculatePrime()
i = 2
#   Set initial all element is prime
while (i < self.limit)
self.primes[i] = true
i += 1
end

i = 2
while (i < self.limit)
if (self.primes[i] == true)
j = 2 * i
while (j < self.limit)
self.primes[j] = false
j += i
end

end

i += 1
end

end

def isCubanPrime(num)
if (num <= 0)
return false
end

if (num < self.limit)
#  When number is under exist limit
return self.primes[num]
end

#  In case number is more than limit.
#  Get square root of number
max = Math.sqrt(num).to_i
i = 3
#  Check that number is cuban primes or not
while (i <= max)
if (self.primes[i] && (num % i) == 0)
return false
end

i += 1
end

#  When number is cuban prime
return true
end

def nthCubanPrime(n)
count = 0
result = 0
num = 0
i = 0
while (count < n)
num = 1 + 3 * i * (i + 1)
if (self.isCubanPrime(num))
result = num
count += 1
end

i += 1
end

print("\n ", n ,"-th cuban prime is ", result)
end

def printCubanPrime(n)
if (n <= 0)
return
end

print("\n  Cuban prime numbers from 1 to ", n ," is \n")
count = 0
i = 0
while (count < n)
num = 1 + 3 * i * (i + 1)
if (self.isCubanPrime(num))
count += 1
print("\t", num)
if (count % 5 == 0)
print("\n")
end

end

i += 1
end

end

end

def main()
#  Test A
#  Print initial 100 cuban prime number
#  Test B
end

main()``````

Output

``````  Cuban prime numbers from 1 to 100 is
7	19	37	61	127
271	331	397	547	631
919	1657	1801	1951	2269
2437	2791	3169	3571	4219
4447	5167	5419	6211	7057
7351	8269	9241	10267	11719
12097	13267	13669	16651	19441
19927	22447	23497	24571	25117
26227	27361	33391	35317	42841
45757	47251	49537	50311	55897
59221	60919	65269	70687	73477
74419	75367	81181	82171	87211
88237	89269	92401	96661	102121
103231	104347	110017	112327	114661
115837	126691	129169	131671	135469
140617	144541	145861	151201	155269
163567	169219	170647	176419	180811
189757	200467	202021	213067	231019
234361	241117	246247	251431	260191
263737	267307	276337	279991	283669

67-th cuban prime is 104347
154-th cuban prime is 812761``````
``````// Scala program for
// Cuban prime numbers
class CubanPrimes(var limit: Int,
var primes: Array[Boolean])
{
def this()
{
this(1000000,Array.fill[Boolean](1000000)(false));
this.calculatePrime();
}
// Pre calculate prime  number under limit
def calculatePrime(): Unit = {
var i: Int = 2;
//  Set initial all element is prime
while (i < this.limit)
{
this.primes(i) = true;
i += 1;
}
i = 2;
while (i < this.limit)
{
if (this.primes(i) == true)
{
var j: Int = 2 * i;
while (j < this.limit)
{
this.primes(j) = false;
j += i;
}
}
i += 1;
}
}
def isCubanPrime(num: Long): Boolean = {
if (num <= 0)
{
return false;
}
if (num < limit)
{
// When number is under exist limit
return primes(num.toInt);
}
// In case number is more than limit.
// Get square root of number
var max: Int = scala.math.sqrt(num).toInt;
var i: Int = 3;
// Check that number is cuban primes or not
while (i <= max)
{
if (primes(i) && (num % i) == 0)
{
return false;
}
i += 1;
}
// When number is cuban prime
return true;
}
def nthCubanPrime(n: Int): Unit = {
var count: Int = 0;
var result: Long = 0;
var num: Long = 0;
var i: Long = 0;
while (count < n)
{
num = 1L + 3 * i * (i + 1);
if (this.isCubanPrime(num))
{
result = num;
count += 1;
}
i += 1;
}
print("\n " + n + "-th cuban prime is " + result);
}
def printCubanPrime(n: Int): Unit = {
if (n <= 0)
{
return;
}
print("\n  Cuban prime numbers from 1 to " + n + " is \n");
var count: Int = 0;
var i: Long = 0;
while (count < n)
{
var num: Long = 1L + 3 * i * (i + 1);
if (this.isCubanPrime(num))
{
count += 1;
print("\t" + num);
if (count % 5 == 0)
{
print("\n");
}
}
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: CubanPrimes = new CubanPrimes();
// Test A
// Print initial 100 cuban prime number
// Test B
}
}``````

Output

``````  Cuban prime numbers from 1 to 100 is
7	19	37	61	127
271	331	397	547	631
919	1657	1801	1951	2269
2437	2791	3169	3571	4219
4447	5167	5419	6211	7057
7351	8269	9241	10267	11719
12097	13267	13669	16651	19441
19927	22447	23497	24571	25117
26227	27361	33391	35317	42841
45757	47251	49537	50311	55897
59221	60919	65269	70687	73477
74419	75367	81181	82171	87211
88237	89269	92401	96661	102121
103231	104347	110017	112327	114661
115837	126691	129169	131671	135469
140617	144541	145861	151201	155269
163567	169219	170647	176419	180811
189757	200467	202021	213067	231019
234361	241117	246247	251431	260191
263737	267307	276337	279991	283669

67-th cuban prime is 104347
154-th cuban prime is 812761``````
``````import Foundation;
// Swift 4 program for
// Cuban prime numbers
class CubanPrimes
{
var limit: Int;
var primes: [Bool];

init()
{
self.limit = 1000000;
self.primes = Array(repeating: false, count: self.limit);
self.calculatePrime();
}
// Pre calculate prime  number under limit
func calculatePrime()
{
var i: Int = 2;
//  Set initial all element is prime
while (i < self.limit)
{
self.primes[i] = true;
i += 1;
}
i = 2;
while (i < self.limit)
{
if (self.primes[i] == true)
{
var j: Int = 2 * i;
while (j < self.limit)
{
self.primes[j] = false;
j += i;
}
}
i += 1;
}
}
func isCubanPrime(_ num: Int) -> Bool
{
if (num <= 0)
{
return false;
}
if (num < self.limit)
{
// When number is under exist limit
return self.primes[num];
}
// In case number is more than limit.
// Get square root of number
let max: Int = Int(sqrt(Double(num)));
var i: Int = 3;
// Check that number is cuban primes or not
while (i <= max)
{
if (self.primes[i] && (num % i) == 0)
{
return false;
}
i += 1;
}
// When number is cuban prime
return true;
}
func nthCubanPrime(_ n: Int)
{
var count: Int = 0;
var result: Int = 0;
var num: Int ;
var i: Int = 0;
while (count < n)
{
num = 1 + 3 * i * (i + 1);
if (self.isCubanPrime(num))
{
result = num;
count += 1;
}
i += 1;
}
print("\n ", n ,"-th cuban prime is ", result, terminator: "");
}
func printCubanPrime(_ n: Int)
{
if (n <= 0)
{
return;
}
print("\n  Cuban prime numbers from 1 to ", n ," is ");
var count: Int = 0;
var i: Int = 0;
while (count < n)
{
let num: Int = 1 + 3 * i * (i + 1);
if (self.isCubanPrime(num))
{
count += 1;
print("\t", num, terminator: "");
if (count % 5 == 0)
{
print(terminator: "\n");
}
}
i += 1;
}
}
}
func main()
{
// Test A
// Print initial 100 cuban prime number
// Test B
}
main();``````

Output

``````  Cuban prime numbers from 1 to  100  is
7	 19	 37	 61	 127
271	 331	 397	 547	 631
919	 1657	 1801	 1951	 2269
2437	 2791	 3169	 3571	 4219
4447	 5167	 5419	 6211	 7057
7351	 8269	 9241	 10267	 11719
12097	 13267	 13669	 16651	 19441
19927	 22447	 23497	 24571	 25117
26227	 27361	 33391	 35317	 42841
45757	 47251	 49537	 50311	 55897
59221	 60919	 65269	 70687	 73477
74419	 75367	 81181	 82171	 87211
88237	 89269	 92401	 96661	 102121
103231	 104347	 110017	 112327	 114661
115837	 126691	 129169	 131671	 135469
140617	 144541	 145861	 151201	 155269
163567	 169219	 170647	 176419	 180811
189757	 200467	 202021	 213067	 231019
234361	 241117	 246247	 251431	 260191
263737	 267307	 276337	 279991	 283669

67 -th cuban prime is  104347
154 -th cuban prime is  812761``````
``````// Kotlin program for
// Cuban prime numbers
class CubanPrimes
{
var limit: Int;
var primes: Array < Boolean > ;

constructor()
{
this.limit = 1000000;
this.primes = Array(this.limit)
{
false
};
this.calculatePrime();
}
// Pre calculate prime  number under limit
fun calculatePrime(): Unit
{
var i: Int = 2;
//  Set initial all element is prime
while (i < this.limit)
{
this.primes[i] = true;
i += 1;
}
i  = 2;
while (i < this.limit)
{
if (this.primes[i] == true)
{
var j: Int = 2 * i;
while (j < this.limit)
{
this.primes[j] = false;
j += i;
}
}
i += 1;
}
}
fun isCubanPrime(num: Long): Boolean
{
if (num <= 0)
{
return false;
}
if (num < this.limit)
{
// When number is under exist limit
return this.primes[num.toInt()];
}
// In case number is more than limit.
// Get square root of number
val max: Int = Math.sqrt(num.toDouble()).toInt();
var i: Int = 3;
// Check that number is cuban primes or not
while (i <= max)
{
if (this.primes[i] && ((num % i)==0L) )
{
return false;
}
i += 1;
}
// When number is cuban prime
return true;
}
fun nthCubanPrime(n: Int): Unit
{
var count: Int = 0;
var result: Long = 0;
var num: Long ;
var i: Long = 0;
while (count < n)
{
num = 1L + 3 * i * (i + 1);
if (this.isCubanPrime(num))
{
result = num;
count += 1;
}
i += 1;
}
print("\n " + n + "-th cuban prime is " + result);
}
fun printCubanPrime(n: Int): Unit
{
if (n <= 0)
{
return;
}
print("\n  Cuban prime numbers from 1 to " + n + " is \n");
var count: Int = 0;
var i: Long = 0;
while (count < n)
{
val num: Long = 1L + 3 * i * (i + 1);
if (this.isCubanPrime(num))
{
count += 1;
print("\t" + num);
if (count % 5 == 0)
{
print("\n");
}
}
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
// Test A
// Print initial 100 cuban prime number
// Test B
}``````

Output

``````  Cuban prime numbers from 1 to 100 is
7	19	37	61	127
271	331	397	547	631
919	1657	1801	1951	2269
2437	2791	3169	3571	4219
4447	5167	5419	6211	7057
7351	8269	9241	10267	11719
12097	13267	13669	16651	19441
19927	22447	23497	24571	25117
26227	27361	33391	35317	42841
45757	47251	49537	50311	55897
59221	60919	65269	70687	73477
74419	75367	81181	82171	87211
88237	89269	92401	96661	102121
103231	104347	110017	112327	114661
115837	126691	129169	131671	135469
140617	144541	145861	151201	155269
163567	169219	170647	176419	180811
189757	200467	202021	213067	231019
234361	241117	246247	251431	260191
263737	267307	276337	279991	283669

67-th cuban prime is 104347
154-th cuban prime is 812761``````

Resultant Output Explanation

The code's output shows two test cases:

1. The first test case prints the initial 100 Cuban prime numbers.
2. The second test case finds and prints the 67th and 154th Cuban prime numbers.

The output is as follows (formatted for better readability):

• The Cuban prime numbers from 1 to 100 are listed in rows of 5 numbers each.
• The 67th Cuban prime is 104347.
• The 154th Cuban prime is 812761.

Time Complexity

1. The 'calculatePrime' method uses the Sieve of Eratosthenes algorithm to find primes up to the given limit. Its time complexity is O(n log log n).
2. The 'isCubanPrime' method checks whether a number is a Cuban prime. If the number is within the pre-calculated prime limit, the lookup operation is O(1). Otherwise, it checks up to the square root of the number, resulting in a time complexity of O(sqrt(n)).
3. The 'nthCubanPrime' method iterates until it finds the nth Cuban prime, which takes O(n) time in the worst case.
4. The 'printCubanPrime' method generates and prints the first n Cuban primes, which takes O(n) time.

Thus, the overall time complexity of the program is dominated by O(n log log n) (from the Sieve) and O(n) (from finding and printing nth Cuban prime or first n Cuban primes). The overall time complexity is approximately O(n log log n) for large values of n.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post