26
Я наткнулся на этот вопрос. Число называется счастливым, если сумма его цифр, а также сумма квадратов его цифр - это простое число. Сколько чисел между A и B повезло? 1 < = A < = B < = 10 . Я попробовал это.
Алгоритм поиска Lucky Numbers
- Сначала я генерироваться все возможные простые числа между 1 и числом, которые могут быть приведены путем суммирования квадратов (81 * 18 = 1458).
- Я прочитал в A и B, чтобы узнать максимальное число, которое может быть сгенерировано путем суммирования цифр. Если B является 2-значным номером (максимальное число равно 18, генерируемому на 99).
- Для каждого простого числа от 1 до максимального числа. Я применил целочисленный алгоритм разбиения.
- Для каждого возможного раздела я проверил, является ли их сумма квадратов их цифр простой. Если это так, то возможны перестановки этого раздела, и если они лежат в радиусе, это удачные числа.
Это реализация:
#include<stdio.h>
#include<malloc.h>
#include<math.h>
#include <stdlib.h>
#include<string.h>
long long luckynumbers;
int primelist[1500];
int checklucky(long long possible,long long a,long long b){
int prime =0;
while(possible>0){
prime+=pow((possible%10),(float)2);
possible/=10;
}
if(primelist[prime]) return 1;
else return 0;
}
long long getmax(int numdigits){
if(numdigits == 0) return 1;
long long maxnum =10;
while(numdigits>1){
maxnum = maxnum *10;
numdigits-=1;
}
return maxnum;
}
void permuteandcheck(char *topermute,int d,long long a,long long b,int digits){
if(d == strlen(topermute)){
long long possible=atoll(topermute);
if(possible >= getmax(strlen(topermute)-1)){ // to skip the case of getting already read numbers like 21 and 021(permuted-210
if(possible >= a && possible <= b){
luckynumbers++;
}
}
}
else{
char lastswap ='\0';
int i;
char temp;
for(i=d;i<strlen(topermute);i++){
if(lastswap == topermute[i])
continue;
else
lastswap = topermute[i];
temp = topermute[d];
topermute[d] = topermute[i];
topermute[i] = temp;
permuteandcheck(topermute,d+1,a,b,digits);
temp = topermute[d];
topermute[d] = topermute[i];
topermute[i] = temp;
}
}
}
void findlucky(long long possible,long long a,long long b,int digits){
int i =0;
if(checklucky(possible,a,b)){
char topermute[18];
sprintf(topermute,"%lld",possible);
permuteandcheck(topermute,0,a,b,digits);
}
}
void partitiongenerator(int k,int n,int numdigits,long long possible,long long a,long long b,int digits){
if(k > n || numdigits > digits-1 || k > 9) return;
if(k == n){
possible+=(k*getmax(numdigits));
findlucky(possible,a,b,digits);
return;
}
partitiongenerator(k,n-k,numdigits+1,(possible + k*getmax(numdigits)),a,b,digits);
partitiongenerator(k+1,n,numdigits,possible,a,b,digits);
}
void calcluckynumbers(long long a,long long b){
int i;
int numdigits = 0;
long long temp = b;
while(temp > 0){
numdigits++;
temp/=10;
}
long long maxnum =getmax(numdigits)-1;
int maxprime=0,minprime =0;
temp = maxnum;
while(temp>0){
maxprime+=(temp%10);
temp/=10;
}
int start = 2;
for(;start <= maxprime ;start++){
if(primelist[start]) {
partitiongenerator(0,start,0,0,a,b,numdigits);
}
}
}
void generateprime(){
int i = 0;
for(i=0;i<1500;i++)
primelist[i] = 1;
primelist[0] = 0;
primelist[1] = 0;
int candidate = 2;
int topCandidate = 1499;
int thisFactor = 2;
while(thisFactor * thisFactor <= topCandidate){
int mark = thisFactor + thisFactor;
while(mark <= topCandidate){
*(primelist + mark) = 0;
mark += thisFactor;
}
thisFactor++;
while(thisFactor <= topCandidate && *(primelist+thisFactor) == 0) thisFactor++;
}
}
int main(){
char input[100];
int cases=0,casedone=0;
long long a,b;
generateprime();
fscanf(stdin,"%d",&cases);
while(casedone < cases){
luckynumbers = 0;
fscanf(stdin,"%lld %lld",&a,&b);
int i =0;
calcluckynumbers(a,b);
casedone++;
}
}
алгоритм слишком медленно. Я думаю, что ответ можно найти на основе свойства чисел. Поделитесь своими мыслями. Спасибо.
Ошибка: 'primelist' имеет размер 1400, но вы относитесь к нему так, как если бы он имел размерность 1500 –
Я думаю, что этот вопрос нужно переместить на http://codereview.stackexchange.com/ –
@Paul R, я не думаю это большое дело – batbaatar