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)
	{
		CubanPrimes task = new CubanPrimes();
		// Test A
		// Print initial 100 cuban prime number
		task.printCubanPrime(100);
		// Test B
		task.nthCubanPrime(67);
		task.nthCubanPrime(154);
	}
}

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()
{
	CubanPrimes *task = new CubanPrimes();
	// Test A
	// Print initial 100 cuban prime number
	task->printCubanPrime(100);
	// Test B
	task->nthCubanPrime(67);
	task->nthCubanPrime(154);
	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)
	{
		CubanPrimes task = new CubanPrimes();
		// Test A
		// Print initial 100 cuban prime number
		task.printCubanPrime(100);
		// Test B
		task.nthCubanPrime(67);
		task.nthCubanPrime(154);
	}
}

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
	task.printCubanPrime(100)
	// Test B
	task.nthCubanPrime(67)
	task.nthCubanPrime(154)
}

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()
{
	$task = new CubanPrimes();
	// Test A
	// Print initial 100 cuban prime number
	$task->printCubanPrime(100);
	// Test B
	$task->nthCubanPrime(67);
	$task->nthCubanPrime(154);
}
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()
{
	var task = new CubanPrimes();
	// Test A
	// Print initial 100 cuban prime number
	task.printCubanPrime(100);
	// Test B
	task.nthCubanPrime(67);
	task.nthCubanPrime(154);
}
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() :
	task = CubanPrimes()
	#  Test A
	#  Print initial 100 cuban prime number
	task.printCubanPrime(100)
	#  Test B
	task.nthCubanPrime(67)
	task.nthCubanPrime(154)

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_reader :limit, :primes
	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() 
	task = CubanPrimes.new()
	#  Test A
	#  Print initial 100 cuban prime number
	task.printCubanPrime(100)
	#  Test B
	task.nthCubanPrime(67)
	task.nthCubanPrime(154)
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
		task.printCubanPrime(100);
		// Test B
		task.nthCubanPrime(67);
		task.nthCubanPrime(154);
	}
}

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()
{
	let task: CubanPrimes = CubanPrimes();
	// Test A
	// Print initial 100 cuban prime number
	task.printCubanPrime(100);
	// Test B
	task.nthCubanPrime(67);
	task.nthCubanPrime(154);
}
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
{
	val task: CubanPrimes = CubanPrimes();
	// Test A
	// Print initial 100 cuban prime number
	task.printCubanPrime(100);
	// Test B
	task.nthCubanPrime(67);
	task.nthCubanPrime(154);
}

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.

New Comment