package javaapplication3;
import java.util.ArrayList;
/**
* 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?
*/
/**
* @author Umang
*/
public class Problem35
{
public static ArrayList<Long> getDigits(long no)
{
ArrayList<Long> numbers = new ArrayList<Long>();
long temp = no;
while (temp > 0)
{
numbers.add(temp % 10);
temp /= 10;
}
return numbers;
}
private static int getCount(long no)
{
ArrayList<Long> numbers = getDigits(no);
return numbers.size();
}
public static long sumOfFactorialOfEach(ArrayList<Integer> numbers)
{
long sum = 0;
for (int no : numbers)
{
sum += factorial(no);
}
return sum;
}
static boolean isPrime(long n)
{
//check if n is a multiple of 2
if (n % 2 == 0)
{
return false;
}
//check the odds
for (long i = 3; i * i <= n; i += 2)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
static String rotate(String number)
{
return number.subSequence(1, number.length()) + "" + number.charAt(0);
}
private static long factorial(long no)
{
return no == 1 ? 1 : no * factorial(no - 1);
}
static boolean checkRotationsAndPrime(long no)
{
boolean allPrimes = true;
String strNo = new Long(no).toString();
int rotations = getCount(no);
for (int i = 0; i < rotations; i++)
{
if (!isPrime(new Long(strNo)))
{
allPrimes = false;
}
strNo = rotate(strNo);
}
return allPrimes;
}
public static void main(String[] args)
{
long count = 0;
for (int i = 1; i <= 1000000; i++)
{
if (checkRotationsAndPrime(i))
{
count++;
}
}
System.out.println("\nCount is " + count);
}
}
|
No comments:
Post a Comment