如何高效计算105以内连续素数的间距总和（基于筛法代码优化）

问题场景 #

现有C语言代码通过埃拉托斯特尼筛法生成105以内的素数，按每行6个的格式打印。当前需求是：

• 统计1-10范围内所有连续素数间距的出现次数（原代码仅统计了间距为4的次数，逐个复制代码统计会冗余）
• 计算所有连续素数的间距总和

现有代码 #

/*
 Program name - sieves.c 
 This program implements the sieve of Eratosthenes algorithm for finding prime numbers.
 The user inputs a number, and the program will print out all prime numbers up to that input and the
 distance between their numbers combined.
*/


#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h> // To measure execution time

#define COLUMNS 6

int column_count = 0;

void print_number(int number){
  printf("%10d ", number);
  column_count++;
  if(column_count%COLUMNS == 0){ // Every 6th entry will yield 0
    printf("\n");
  }
}

// The function that implements the sieve of Eratosthenes algorithm.
// This function has one parameter that states the max prime number values.

void print_sieves(int input)
   {
    // Initialize the array we will work with
    int array_size = input - 1;
    // Local array declaration
    char numbers[array_size];

    // Populate the array with 1's (True values)
    for(int entry = 0; entry < array_size; entry++){
      numbers[entry] = 1;
    }

    // Check the factors up to the square of the input, since that is
    // the last number that can be squared to produce the input.
    for(int i = 2; i <= (int) sqrt(input); i++){
      if(numbers[i] == 1){ // This is to check if we already covered a number
        for(int j = i*i; j <= input; j+=i){ // For every multiple of that number
          numbers[j] = 0; // Mark it as non-prime
        }
      }
    }

    // Printing out the true values from the array, starting from the "2"
    for(int i = 2; i <= array_size; i++){
      if(numbers[i] == 1){
        print_number(i);
      }
    }

    // Print out how many occurences of a length of 4 between the primes.
    int steps = 0;
    int x = 0; // prime x < y
    for(int y = 2; y <= array_size; y++){
      if(numbers[y] == 1){ // When we get to next prime
        if(y - x == 4){
          steps++;
        }
        x = y; // assign x to y so we calculate from there next time
      }
    }

    printf("\n\nNumber of occurences with 4 steps between primes: %d\n", steps);
}

// 'argc' contains the number of program arguments, and
// 'argv' is an array of char pointers, where each
// char pointer points to a null-terminated string.
int main(int argc, char *argv[])
{
  // Uncomment this segment below for using input in terminal
  /* if(argc == 2)
    print_primes(atoi(argv[1]));
  else
    printf("Please state an interger number.\n"); 
  */

  print_sieves(105);
  return 0;
}

优化方案 #

核心思路是用数组计数代替重复的条件判断，一次遍历完成所有间距的统计，同时计算总间距和：

1. 定义一个计数数组gap_counts，索引对应间距值（比如gap_counts[4]统计间距4的次数），初始化为0
2. 遍历素数时，计算当前素数与上一个素数的间距gap
3. 如果gap在1-10范围内，就给gap_counts[gap]加1，同时累加总间距和
4. 最后循环打印所有1-10间距的出现次数，以及总间距和

修改后的完整代码 #

/*
 Program name - sieves.c 
 This program implements the sieve of Eratosthenes algorithm for finding prime numbers.
 The user inputs a number, and the program will print out all prime numbers up to that input,
 count occurrences of prime gaps (1-10), and calculate total gap sum.
*/


#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h> // To measure execution time

#define COLUMNS 6
#define MAX_GAP 10 // 要统计的最大间距

int column_count = 0;

void print_number(int number){
  printf("%10d ", number);
  column_count++;
  if(column_count % COLUMNS == 0){ // 每6个数字换行
    printf("\n");
  }
}

void print_sieves(int input)
{
    // Initialize the array we will work with
    int array_size = input - 1;
    char numbers[array_size];

    // Populate the array with 1's (mark as prime initially)
    for(int entry = 0; entry < array_size; entry++){
      numbers[entry] = 1;
    }

    // Sieve of Eratosthenes core logic
    for(int i = 2; i <= (int)sqrt(input); i++){
      if(numbers[i] == 1){ // Only process unmarked numbers
        for(int j = i*i; j <= input; j += i){ // Mark multiples as non-prime
          numbers[j] = 0;
        }
      }
    }

    // Print primes in 6-column format
    printf("Primes up to %d:\n", input);
    for(int i = 2; i <= array_size; i++){
      if(numbers[i] == 1){
        print_number(i);
      }
    }
    printf("\n");

    // Initialize gap counting variables
    int gap_counts[MAX_GAP + 1] = {0}; // 索引0不用，1-10对应间距值
    long long total_gap_sum = 0;
    int last_prime = 0;

    // Traverse primes to count gaps and calculate total sum
    for(int y = 2; y <= array_size; y++){
      if(numbers[y] == 1){
        if(last_prime != 0){ // Skip first prime (no previous prime)
          int gap = y - last_prime;
          total_gap_sum += gap;
          // 只统计1-10范围内的间距
          if(gap >= 1 && gap <= MAX_GAP){
            gap_counts[gap]++;
          }
        }
        last_prime = y;
      }
    }

    // Print gap statistics
    printf("\nPrime gap occurrences (1-%d):\n", MAX_GAP);
    for(int gap = 1; gap <= MAX_GAP; gap++){
      printf("Gap %d: %d times\n", gap, gap_counts[gap]);
    }

    // Print total gap sum
    printf("\nTotal sum of all consecutive prime gaps: %lld\n", total_gap_sum);
}

int main(int argc, char *argv[])
{
  // Uncomment below to use command-line input
  /* if(argc == 2)
    print_sieves(atoi(argv[1]));
  else
    printf("Please enter an integer number.\n"); 
  */

  print_sieves(105);
  return 0;
}

说明 #

• 代码中定义了MAX_GAP宏，方便调整要统计的最大间距范围
• 用数组gap_counts一次性完成所有间距的统计，避免了冗余的条件判断
• 新增了总间距和的计算，满足需求
• 打印格式更清晰，区分了素数列表、间距统计和总间距和

内容的提问来源于stack exchange，提问作者techgeeknoob