Lucky Numbers
Lucky Numbers
+ 6 comments why 23 in between 21 and 25 is not lucky number,
as we are getting digit sum 5, and sum of square of digits are 13.
+ 2 comments I made this code in C. It works with the sample case, but I fail in all the test cases due to timeout. Why is that?
#include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #include <assert.h> #include <inttypes.h> int checkPrime(uint64_t s){ /*gets a number and return 1 for prime or 0 otherwise*/ uint64_t i; if (s <= 1) return 0; if (s == 2) return 1; if (s % 2 == 0 && s > 2) return 0; else for (i = 3; i < s/2; i += 2){ if (s % i == 0) return 0; } return 1; } int sumSqrDigits(uint64_t a){ /* sum the square of all digits of a number*/ uint64_t s = 0; if (a <= 10) return 0; while (a > 0){ s += (a%10)*(a%10); a = a/10; } return checkPrime(s); /* checks if the sum is a prime number*/ } int sumDigits(uint64_t a){ //sum the digits of a number uint64_t s = 0; if (a <= 10) return 0; else while (a > 0){ s += a%10; a = a/10; } return checkPrime(s); /* checks if the sum is a prime number*/ } int luckyNumbers(uint64_t a, uint64_t b) { /*iterates through all numbers between a and b (included)*/ uint64_t ans = 0, i; for (i = a; i <= b; i++){ if ((sumDigits(i) == 1) && (sumSqrDigits(i) == 1)){ // checks if both results are prime ans++; //printf("%"PRIu64"\n", ans); } } return ans; } int main() { uint64_t a, b, i, cases; scanf("%"SCNu64, &cases); uint64_t ans[cases]; for(i = 0; i < cases; i++) { scanf("%"SCNu64 "%"SCNu64 , &a, &b); ans[i] = luckyNumbers(a, b); } for (i = 0; i < cases; i++){ printf("%"PRIu64"\n", ans[i]); } return 0; }
+ 0 comments #include <bits/stdc++.h> using namespace std; typedef long long LL; const int max_num = 1458; const int max_sum = 162; const int max_length = 19; LL dp[max_length + 1][max_sum + 1][max_num + 1]; int digits[max_length + 1]; bool composite[max_num + 1]; int len; void get_primes(){ composite[0] = composite[1] = true; for(long long i = 2; i * i <= max_num; i++){ if(!composite[i]){ for(long long j = i * i; j <= max_num; j+= i){ composite[j] = true; } } } } LL rec(int pos, int s1, int s2, int chk) { if(pos == -1) return !composite[s1] && !composite[s2]; if(!chk && dp[pos][s1][s2] != -1) return dp[pos][s1][s2]; LL ans = 0; int end = chk ? digits[pos] : 9; for(int d = 0 ; d <= end; d++) { ans += rec(pos - 1 , s1 + d , s2 + d * d, chk && d == end); } if(!chk) dp[pos][s1][s2] = ans; return ans; } LL get_ans(LL num) { if(num == 0) return 0; len = 0; while(num){ digits[len++] = num % 10; num /= 10; } LL ans = rec(len - 1, 0, 0, 1); return ans; } int main() { ios::sync_with_stdio(false);cin.tie(0); int t; get_primes(); memset(dp,-1,sizeof(dp)); cin >> t; while(t--) { LL a, b; cin >> a >> b; cout << get_ans(b) - get_ans(a - 1) << endl; } return 0; }
+ 0 comments If my calculations are right...
A and B <= 10**18 that means the biggest sum of digits is 999 999 999 999 999 999 (i.e 18 nines). So the biggest number to check as prime is the sum of eighteen squares of nines:
9*9*18 = 1458
spoiler: 1458 is not prime but 231 numbers below 1458 are prime. Not too many... to store in a list. You can calculate them or copy from here or whatever source you choose:
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453]
Checking if number is in the list of primes will save you a for loop check, reducing therefore time complexity of your code.
Another spoiler: although it is more efficient than a foor loop prime checker, this won't save you to timeout if you loop between A =1 and B =10^18 stepping +1.
Edit: as stated by @abhiranjan 4 years ago 10^18 instructions may take ~316 years to solve by modern computers. Even them where 32 years or 3 years is unpractical to wait compute that long.
We need something better.
+ 0 comments 13 is a prime number and so is 5 so why isn't 23 considered a "lucky" number 23 5 4,9 13
Sort 69 Discussions, By:
Please Login in order to post a comment