Problem 35(Circular primes)

Problem 35(Circular primes)

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

 

In Python:

import time
import math

startTime = time.time()

def circular(n):
    nStr = str(n)
    return int((nStr[-1] + nStr)[:-1])

def isprime(n):
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def iscircularprime(n):
    count = 0
    digit = int(math.log10(n)) + 1
    for i in range(0, digit):
        if isprime(n) is False:
            break
        n = circular(n)
        count += 1
    if count == digit:
        return True

list = [2]
for n in range(3, 10 ** 6, 2):
    if iscircularprime(n) is True:
        list.append(n)

print(len(list))
print(time.time() - startTime, "seconds")

Run time: 7.69934606552124 seconds

 

 

In Python:

import time
import math

startTime = time.time()

def circular(n):
    nStr = str(n)
    return int((nStr[-1] + nStr)[:-1])

def isprime(n):
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def iscircularprime(n):
    count = 0
    digit = int(math.log10(n)) + 1
    for i in range(0, digit):
        if isprime(n) is False:
            break
        n = circular(n)
        count += 1
    if count == digit:
        return True

list = []
primeCheck = [1 for i in range(2, 10 ** 6)]
for n in range(2, 10 ** 6):
    if primeCheck[n - 2] == 0:
        continue
    else:
        if iscircularprime(n) is True:
            list.append(n)
        q = (10 ** 6) // n
        for i in range(1, q):
            primeCheck[n * i - 2] == 0
print(len(list))
print(time.time() - startTime, "seconds")

Run time: 12.151581764221191 seconds

 

In Java:

//Euler35 Circular primes
package project_euler31_40;

import java.util.ArrayList;
import java.math.*;

public class Euler35 {
	public static Boolean isprime(int n) {
		for (int i = 2; i < Math.sqrt(n) + 1; i++) {
			if (n % i == 0) {
				return false;
			}
		}
		return true;
	}
	public static int circular(int n) {
		int firstNum;
		String nStr = "";
		String data[];
		ArrayList<Integer> nList1 = new ArrayList<Integer>();
		ArrayList<Integer> nList2 = new ArrayList<Integer>();

		nStr = Integer.toString(n);
		data = nStr.split("");
		for (int i = 0; i < data.length; i++) {
			nList1.add(Integer.parseInt(data[i]));
		}
		firstNum = nList1.get(0);
		nList2.addAll(nList1.subList(1, nList1.size()));
		nList2.add(firstNum);
		n = 0;
		for (int i = 0; i < nList2.size(); i++) {
			n = n * 10 + nList2.get(i);
		}
		return n;
	}
	public static Boolean iscircularprime(int n) {
		int count = 0;
		int digit = (int) Math.log10(n) + 1;
		int div = 0;
		int r = 0;
		div = n;
		for (int i = 0; i < digit; i++) {
			r = Math.floorMod(div, 10);
			if (r == 0) {
				return false;
			}
			div = Math.floorDiv(div, 10);
		}
		for (int i = 0; i < digit; i++) {
			if (isprime(n) == false) {
				break;
			}
			n = circular(n);
			count ++;
		}
		if (count == digit) {
			return true;
		} else {
			return false;
		}
	}
	public static void main(String[] args) {
		long startTime = System.currentTimeMillis();
		ArrayList<Integer> resultList = new ArrayList<Integer>();
		resultList.add(2);
		for (int n = 3; n < Math.pow(10, 6); n += 2) {
			if (iscircularprime(n) == true) {
				resultList.add(n);
			}
		}
		System.out.println(resultList.size());
		long endTime = System.currentTimeMillis();
		System.out.println((double)(endTime - startTime)/(double)1000 + "seconds");
	}
}

Run time: 0.808seconds

 

Solution: 55