Project Euler #35: Circular primes Discussions |

Sort 31 Discussions, By:

3 weeks ago+ 0 comments

100 points.

lookup=[0]*1000001
sieve=[False,True,False,True]*250001
for i in range(3,1001,2):
    if sieve[i]:
        for j in range(i*i,1000001,i):
            sieve[j]=False
sieve[1],sieve[2]=False,True
for p in range(2,1000001):
    if sieve[p]:
        if len(str(p))==0:
            lookup[p]+=p
        else:
            for i in range(1,len(str(p))):
                c=int(str(p)[i:]+str(p)[:i])
                if not sieve[c]:
                    break
            else:
                lookup[p]+=p             
    lookup[p]+=lookup[p-1]

n=int(input().strip())
print(lookup[n])

1 month ago+ 0 comments

(Here's another dumb ass, that posts its code).
Python3. Note that digits must be odd.

from itertools import product

def do_sieve(n=10**6):
    sieve = [False, True, False, True] * (n//4 + 1)
    nroot = int((n+1)**.5)
    for p in range(3, nroot +1, 2):
        if sieve[p]:
            for i in range(p*p, n+1, p): sieve[i] = False
    return sieve

n = int(input())

prime = do_sieve(n)
s = 2+3+5+7

for l in range(2, len(str(n)) +1):
    for cand in product('13579', repeat=l):
        p = int(''.join(cand))
        if int(p) >= n: break
        for _ in range(l):
            if not prime[p]: break
            cand = cand[1:] + (cand[0],)
            p = int(''.join(cand))
        else:
            s += p

print(s)

2 months ago+ 0 comments

JAva code

import java.io.*;
import java.util.*;

public class Solution {

       static boolean isPrime(int x) {
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

    static boolean areAllRotationsPrime(int x) {
        int d = 1;
        int num = x;
        int digits = 0;

        while (d <= num) {
            d *= 10;
            digits++;
        }
        d /= 10;

        for (int k = 0; k < digits; k++) {
            int rotation = (x % 10) * d + (x / 10);
            if (!isPrime(rotation)) {
                return false;
            }
            x = rotation;
        }

        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int sum = 0;

        for (int i = 2; i < n; i++) {
            if (isPrime(i) && areAllRotationsPrime(i)) {
                sum += i;
            }
        }

        System.out.println(sum);
        scanner.close();
    }
}

4 months ago+ 0 comments

def isprime(n):

if n < 2 :

    return(False)

if n == 2 :

    return(True)

if n % 2 == 0 :

    return(False)

for i in range(3, int(n**0.5)+1 , 2):

    if n % i == 0 :

        return(False)

return(True)

def iscircular (n) :

ch=str(n)

l=[]

for i in range(len(ch)) :

    rotated_str = ch[i:] + ch[:i]

    l.append(int(rotated_str))

for e in l :

    if not isprime(e) :

        return(False)

return(True)

n=int(input())

d={10:17}

s=17

for i in range(11,10**6 +1):

d[i]=s

if iscircular (i) :

    s+=i

print(d[n])

4 months ago+ 0 comments

here is my c# 100 point answer

using System;

class Solution {
    static bool IsPrime(int x) {
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

    static bool AreAllRotationsPrime(int x) {
        int d = 1;
        int num = x;
        int digits = 0;
        
        while (d <= num) {
            d *= 10;
            digits++;
        }
        d /= 10;

        for (int k = 0; k < digits; k++) {
            int rotation = (x % 10) * d + (x / 10);
            if (!IsPrime(rotation)) {
                return false;
            }
            x = rotation;
        }

        return true;
    }

    static void Main(string[] args) {
        int n = int.Parse(Console.ReadLine());
        int sum = 0;

        for (int i = 2; i < n; i++) {
            if (IsPrime(i) && AreAllRotationsPrime(i)) {
                sum += i;
            }
        }

        Console.WriteLine(sum);
    }
}

Load more conversations