Labels

Project Euler #35: Circular primes

Question
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?

Answer : 55

Hacker Rank Problem

Solution


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long res = 0;

        for(int i=2;i<n;i++)
        {
            if(isPrime(i))
            {
                if(isCircularPrime(i))
                    res+=i;
            }
        }
        System.out.println(res);
    }

    public static boolean isCircularPrime(int n)
    {
        String s = String.valueOf(n);
        char[] arr = s.toCharArray();
        int rotation = 0;
        while(rotation<s.length())
        {
            arr = getNextRotation(arr);
            if(!isPrime(Long.valueOf(new String(arr)))) return false;
            rotation+=1;
        }
        return true;
    }

    public static char[] getNextRotation(char[] arr)
    {
        if(arr.length>1)
        {
            char temp = arr[0];
            for(int i=0;i<arr.length-1;i++)
            {
                arr[i] = arr[i+1];
            }
            arr[arr.length-1] = temp;
        }
        return arr;
    }

    public static boolean isPrime(long num)
    {
        try
        {
            if ( num > 2 && num%2 == 0 ) return false;
            int top = (int)Math.sqrt(num) + 1;
            for(int i = 3; i < top; i+=2)
            {
                if(num % i == 0)
                {
                    return false;
                }
            }
            return true;
        }
        catch(Exception e)
        {
            throw e;
        }
    }
}
Labels:

Comments

Post a Comment

Popular Posts