We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Project Euler #35: Circular primes
Project Euler #35: Circular primes
+ 0 comments - When finding rotations of a number, don't forget about zeroes in the middle. You should rotate honestly including zeroes (example for a not prime number):
104080 -> 040801, 408010, 080104, 801040, 010408
- Use memoization in the isprime() function. You will have overhead otherwise.
+ 0 comments Use sieve of eratosthenes, find whether the number and their rotations are prime and add them to a set and find the sum. I have the code in Python if you don't understand~
+ 0 comments Hey! I was stucked in this problem and so frustrated So, here is the solution (in c++)
int prime(int x){ for(int i=2;i*i<=x;i++){ if(x%i == 0) return false; } return true; } int p(int x){ int d = 1; int digs = 0; while(d <= x){ d *= 10; digs++; } d/=10; for(int k=0;k
THANKS ME LATER! //cout << i <<endl; } } printf("%d\n", sum);
+ 0 comments Python O(1) sol:
n = int(input()) e = sorted([2,3,5,7,11,13,31,37,17,71,73,79,97,113,131,311,197,971,719,199,991,919,337,373,733,1193,1931,9311,3119,3779,7793,7937,9377,11939,19391,93911,39119,91193,19937,99371,93719,37199,71993,193939,939391,393919,939193,391939,919393,199933,999331,993319,933199,331999,319993,]) res = 0 for i in e: if i <= n: res += i else: break print(res)
+ 0 comments C++ Solution :
#include <bits/stdc++.h> using namespace std; #define all(v) (v).begin(), (v).end() #define debug(x) cout << #x << " = " << x << endl typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; inline ll Mod(ll x, ll mod) { return x % mod >= 0 ? x % mod : x % mod + mod; } bool *is_prime = new bool[1000001]; void sieve(int N) { for (int i = 0; i <= N; i++) is_prime[i] = 1; is_prime[0] = 0; is_prime[1] = 0; for (int i = 2; i * i <= N; ++i) { if (is_prime[i]) { for (int j = i * i; j <= N; j += i) is_prime[j] = 0; } } } bool is_rotate(int n, int p) { for (int i = 0; i < 7; i++) { int y = n % 10; n /= 10; n += y * p; if (!is_prime[n]) return 0; } return 1; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); sieve(1000000); ll *ans = new ll[1000001]; memset(ans, 0, sizeof(ans)); int p = 1; for (int i = 2; i < 1000001; i++) { if (i == p * 10) p *= 10; if (is_prime[i] == 0 || is_rotate(i, p) == 0) { ans[i] = ans[i - 1]; continue; } ans[i] = ans[i - 1] + i; } int n; cin >> n; cout << ans[n]; }
Load more conversations
Sort 25 Discussions, By:
Please Login in order to post a comment