You are using the new UI (Beta).Return to the original UI

This page has been automatically translated by machine translation. Please note that translations may not be entirely accurate.

keisanHigh-precision calculations for everyday life and work

List prime numbers up to 1 million

Author: ameyaExecutions: 13362

※ This library was created by a member. This site is not responsible for its content.

Manage Bookmarks
It can display prime numbers up to 1 million using the Sieve of Eratosthenes.
Starting from 2
Displays all prime numbers between these values.
It uses a performance-optimization technique called the “Wheel Sieve.” I think.
I didn’t quite understand the English explanation, but I pieced it together based on an image I found on Wikipedia.

/* First, prepare an array called `Wheel` consisting of natural numbers up to 2*3*5*7=210, excluding multiples of 2, 3, 5, and 7. Due to the processing logic, the array goes up to 211, but this is simply “210+1,” and it just so happens to be the next prime number. */
numeric wheel[] = {1, 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, 121, 127, 131, 137, 139, 143, 149, 151,157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209, 211};
/* Number of elements in `Wheel` */
whlen = 48;
/* Prepare an array of (half the difference) values (the starting index is shifted by one for convenience; there are two iterations because the rotation process is cumbersome)*/
numeric ntb105[] = {1,2,1,2,3,1,3,2,1,2,3,3,1,3,2,1,3,2,3,4,2,1,2,1,2,4,3,2,3,1,2,3,1,3,3,2,1,2,3,1,3,2,1,2,1,5,1,5,1,2,1,2,3,1,3,2,1,2,3,3,1,3,2,1,3,2,3,4,2,1,2,1,2,4,3,2,3,1,2,3,1,3,3,2,1,2,3,1,3,2,1,2,1,5,1,5};
/* Also create a table to map sieve indices to positions on the wheel */
numeric nrev105[105];
for (k = 1; k <= whlen; k = k + 1) {
  nrev105[(wheel[k] - 3) / 2] = k - 1;
}
/* Then just spin it around, sort of */
numeric numx[48];
idx = 4;
while (idx < enphsiev) {
  for (z = 0; z < whlen; z = z + 1) {
    if (sieve[idx] == 0) {
      m = nrev105[mod(idx, 105)];    /* Starting position of the wheel */
      num = idx * 2 + 3;        /* This expression converts the sieve index to the actual number */
      j = ((num * num) - 3) / 2;     /* This reverses the squaring process to convert back to the index */
      for (k = 0; k < whlen; k = k + 1) {
        numx[k] = ntb105[m + k] * num; /* Since multiplication is computationally expensive, we use a lookup table */
      }
      while (j < sievemax) {      /* Main loop of the sieve */
        for (k = 0; k < whlen; k = k + 1) {
          sieve[j] = 1;
          j = j + numx[k];
        }
      }
    }
    idx = idx + ntb105[z];
    if (idx >= enphsiev) {break;}
  }
}
* The sieve array `sieve[idx]` corresponds to `idx=0 → 3`, `idx=1 → 5`, `idx=2 → 7`, and so on.
*Note: In the main loop, the argument `j` for `sieve[j]` can exceed `maxsieve` by up to `whlen-1`, so some measure must be taken to address this.
*Note: To complete the program, the following code and the code to display the results are required.
/* Assuming the input variable is `UpperLimit` */
sievemax = ceiling(UpperLimit / 2);
enphsiev = int(sqrt(UpperLimit) / 2);
/* It appears that the input value is treated as a constant until it is changed, so it can be used as an array index */
numeric sieve[UpperLimit];

No customer feedback for this calculation yet.