Блог

/Написать программу для определения общего числа простых чисел ниже 1000 000 000, сумма цифр которых равна 14? Убедитесь, что время выполнения составляет несколько секунд./

 #include<stdio.h>
#include<math.h>

int main() {
  int i, j, count = 0, temp = 0, n, ans = 0, tot = 0;
  for (i = 1; i <= 1000000000; i  ) {
    for (j = 2; j <= i / 2; j  ) {
      if (i % j == 0) {
        count  ;
      }
    }

    if (count == 0) {
      n = i;
      while (n != 0) {
        temp = n % 10;
        n = n / 10;
        ans = ans   temp;
      }
      if (ans == 14) {
        tot  ;
        printf("%d,", i);
      }
      ans = 0;
      temp = 0;
    }
    count = 0;
  }
  // printf("%d:n",tot);
  return 0;
}
 

Два простых улучшения (среди прочего):

1: Вместо того , чтобы повторять i/2 , повторяйте до квадратного корня из i — то есть j*j <= i .^** Это огромное ускорение.

2: Завершите цикл, как только фактор найден.

 // for(j=2;j<=i/2;j  ) {
//  if(i%j==0) {
//    count  ;
//  }
//}
for(j=2;j<=i/j;j  ) { // _much_ lower limit
  if(i%j==0) {
    count  ;
    break; // No need to find more factors: `i` is not a prime.
  }
}
 

Функциональность: Внутри if(count==0) , я бы ожидал ans == 0 раньше while(n!=0) .

^** Используйте j<=i/j для предотвращения переполнения. Хороший компилятор увидит поблизости i%j и часто выполнит и i/j, i%j то, и другое за счет временных затрат.

Функция суммирования цифр также может использовать раннее возвращение, например:

    int dsum14(int n) {
        int sum = 0;
        for (; n; n /= 10)
            if ((sum  = n % 10) > 14)
                return 0;
        return sum == 14 ? 1 : 0;
    }
 

Но как совместить (эффективный) простой поиск и это условие суммы?

 int n, cnt = 0;
for (n = 3; n < 1000*1000*1000; n  = 2)
    if (n%3 amp;amp; n%5 amp;amp; dsum14(n) amp;amp; n%7 amp;amp; n amp;amp; n)
        cnt  ;
 

Это дает 77469 результат за 1,5 секунды. При dsum() этом на обоих концах логической цепочки она почти удваивается.

amp;amp; n%7 amp;amp; n amp;amp; n Часть будет заменена функцией, использующей список простых чисел примерно до 32000 (квадратный корень из макс.).

…или вы можете оптимизировать его до 0,1 секунды, настроив функцию digsum.

Существует «всего» 575 трехзначных чисел 000-999 с суммой 14 или менее. Поэтому я готовлю их и объединяю три из них, чтобы получить 9-значное число. Генерировать их вместо фильтрации.

Хвост выглядит как:

 920000021
920000201
920001011
920010011
920100011
920100101
920101001
921001001
931000001
total count: 22588

real    0m0.098s
user    0m0.100s
sys     0m0.002s
 

И начало:

 59
149
167
239
257
293
347
383
419
 

Не на 100% уверен, что это правильно, но общее количество также кажется разумным.

Все это зависит от заданного максимума в 1000 миллионов. digsum_prime() использует его для построения номера кандидата из трех (почти) равных частей.

Код:

 #include <stdio.h>
#include <stdlib.h>

int parr[5000] = {3};

struct {
    int tri, sum;
} ts[999]; 

void primarr(void) {
    int maxn = 32000;
    int i = 1;
    for (int n = 5; n < maxn; n  = 2)
        for (int div = 3;; div  = 2) {
            if (!(n % div))
                break;
            if (div*div > n) {
                parr[i  ] = n;
                break;
            }
        }    
}

int isprime(int n) {
    for(int i = 0;; i  ) {
        if (!(n % parr[i]))
            return 0;
        if (parr[i]*parr[i] > n)
            return 1;
    }
}

int dsum(int n) {
    int sum = 0;
    for (; n; n /= 10) 
        sum  = n % 10;
    return sum;
}
int tsarr(void) {
    int i = 0;
    for (int n = 0; n < 1000; n  ) {
        int digsum = dsum(n);
        if (digsum <= 14) {
            ts[i].tri = n;
            ts[i].sum = digsum;
            i  ;
        }
    }    
    return i;
}

int digsum_prime() {

    int cnt = 0;
    int tslen = tsarr();
    printf("tslen: %dn", tslen);

    int high, mid, low;
    int sum, num;

    for (high = 0; high < tslen; high  ) { 

        if(ts[high].sum > 13)
            continue;
        for (mid = 0; mid < tslen; mid  ) { 

            if(ts[mid].sum   ts[high].sum > 13)
                continue;
            sum = ts[mid].sum   ts[high].sum;

            for (low = 0; low < tslen; low  )   
                if (ts[low].tri % 2) 
                    if(ts[low].sum   sum == 14) {

                        num = ts[high].tri * 1000*1000 
                              ts[mid] .tri * 1000 
                              ts[low] .tri;

                        if (isprime(num)) {
                            cnt  ;        
                            printf("%dn", num);
                        }
                    }
        }
    }
    
    return cnt; 
}

int main(void) {
    primarr();
    printf("total count: %dn", digsum_prime());

}
 

Изменение 13-13-14 на 3-3-4 (но та же часть подготовки) дает обзор — за 0,005 с!

 tslen: 575
13
31
103
211
1021
1201
2011
3001
10111
20011
20101
21001
100003
102001
1000003
1011001
1020001
1100101
2100001
10010101
10100011
20001001
30000001
101001001
200001001
total count: 25

real    0m0.005s
user    0m0.005s
sys     0m0.000s
 

Make sure the execution time is few seconds.

oops

But the limits of OP are well chosen: a naive approach takes several seconds.