Jego założenie polega na wykorzystaniu powtarzalności cyfr w szeregach liczb pierwszych ułożonych czwórkami na każdy kolejny rząd dzisięciu liczb naturalnych.
Mamy liczby naturalne n i zwiększymy rzędy co 10 dodając kolejną czwórkę liczb z końcówkami 1,3,7,9.
QR => (n*10)+1,(n*10)+3,(n*10)+7,(n*10)+9
QR - quadruple row - rząd czwórki
n - liczba naturalna
Nie wiem jak to lepiej zapisać jako funkcję SIGMA w Lateksie. Może ktoś pomoże.
Oto kod źródłowy:
Kod: Zaznacz cały
// Calculate Primes set at given limit and show it as a sets of four in a row (n*10)+1,(n*10)+3,(n*10)+7,(n*10)+9
//
// PTOQR - PRIME NUMBERS TO QUADRUPLE ROWS
// Author: MARTE.BEST - Sylwester Bogusiak aka Sylvi91 with use STD math library
// There is no warranty or guarantee of any kind.
// To Compile:
// gcc -o ptoqr ptoqr.c -lm
// Usage:
// ./ptoqr 1 1000
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#ifdef __APPLE__
#include <mach/mach_time.h>
#else
#include <time.h>
#endif
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// IS THIS PRIME NUMBER - CLASSICAL VERSION
int is_this_prime_number(int natural_number)
{
int n, i, flag = 0;
n=natural_number;
for(i=2; i<=n/2; ++i)
{
// condition for nonprime number
if(n%i==0)
{
flag=1;
break;
}
}
if (flag==0)
return 0; // 0 - jest prime
else
return 1;
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// IS THIS PRIME NUMBER 3-7 FOR 1379 METHOD AKA PTOQR
int is_this_prime_number_3_7(unsigned long long int natural_number)
{
unsigned long long int i, n, flag = 0;
n=natural_number;
// condition for nonprime number
if((n%3==0) || (n%7==0))
{
flag=1; // 1 - nonprime
return 1;
}
for(i=11; i<=sqrt(n); i=i+2)
{
// condition for nonprime number
if(n%i==0)
{
flag=1;
break;
}
}
if (flag==0)
return 0; // 0 - is prime
else
return 1;
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// CALCULATE AND DISPLAY PRIMES
int calc_primes_1379(unsigned long long int begin, unsigned long long int end)
{
unsigned long long int i,n;
unsigned long long int a;
unsigned long long int row_sum=0; // sum of prime numbers in a row
unsigned long long int row_qty=0; // qty of prime numbers in a row
unsigned long long int total_qty=0; // total qty of prime numbers
int four[4] = {1,3,7,9};
if ((end>=begin) && (begin>=1))
{
printf("________________________________________________________________________\n");
printf("______________________ PTO1379 aka PTOQR v.0.1 BETA ____________________\n");
printf("____________________ PRIME NUMBERS TO QUADRUPLE ROWS ___________________\n");
printf("____________ THAT APP IS CALCULATING THE PRIME NUMBERS _________________\n");
printf("_____ AND DISPLAYS IT AS 4 COLUMNS OF INTEGERS ENDED WITH 1,3,7,9 ______\n");
printf("____________ Author: MARTE.BEST - Sylwester B aka Sylvi91 ______________\n");
printf("________________________________________________________________________\n");
printf("_______________ Please wait. Warning! _______________\n");
printf("__ For end limit greater than 100000000 this may take couple minutes. __\n");
printf("_______________ Bigger limit consume more and more time. _______________\n");
printf("________________________________________________________________________\n");
//print on screen
printf("* - PRIME, n - natural number\n ");
printf(" integers sum qty\n ");
if (begin == 1)
{
printf(" *2,*3,*5,*7, 17 4,\n ");
total_qty = 4;
}
for (n = begin; n < end; n ++)
{
row_sum=0;
row_qty=0;
for (i = 0; i < 4; i ++)
{
a = (n * 10) + four[i];
if (!is_this_prime_number_3_7(a)) // faster over 100 to 1000 times
// if (!is_this_prime_number(a)) // very slow
{
row_sum += a; row_qty++;
printf(" *%llu, ", a);
total_qty++;
//printf("*");
}
else
{
printf(" n%llu, ", a);
//printf(" ");
}
}
printf(" %llu, ", row_sum);
printf(" %llu, ", row_qty);
printf("\n ");
}
printf(" Total primes quantity between %llu and %llu is equal to: %llu ", begin, end * 10, total_qty);
printf("\n ");
}
else
{
printf("Set properly begin and end of rows\n ");
}
return 0;
}
int main(int argc, char * argv[]) {
unsigned long long int b;
unsigned long long int e;
if (argc <= 2)
{
printf ("Usage: %s <begin of rows> <end of rows>\n", argv[0]);
return 1;
}
b=atol(argv[1]);
e=atol(argv[2]);
assert(b >= 1);
assert(e >= 2);
// Get system time START
#ifdef __APPLE__
uint64_t start = mach_absolute_time();
#else
clock_t start = clock();
#endif
calc_primes_1379(b,e); // Change the arguments b and e to adjust the begin and end of rows [1,3,7,9]
// Get system time END
#ifdef __APPLE__
uint64_t end = mach_absolute_time();
mach_timebase_info_data_t timebase_info;
mach_timebase_info(&timebase_info);
long double diff = (end - start) * timebase_info.numer / timebase_info.denom; // nano sec
printf("Your calculations took %.3Lf seconds to run.\n", diff / 1e9 );
#else
clock_t end = clock();
printf("Your calculations took %.3Lf seconds to run.\n", (long double)(end - start) / CLOCKS_PER_SEC );
#endif
return 0;
}
Kod: Zaznacz cały
________________________________________________________________________
______________________ PTO1379 aka PTOQR v.0.1 BETA ____________________
____________________ PRIME NUMBERS TO QUADRUPLE ROWS ___________________
____________ THAT APP IS CALCULATING THE PRIME NUMBERS _________________
_____ AND DISPLAYS IT AS 4 COLUMNS OF INTEGERS ENDED WITH 1,3,7,9 ______
____________ Author: MARTE.BEST - Sylwester B aka Sylvi91 ______________
________________________________________________________________________
_______________ Please wait. Warning! _______________
__ For end limit greater than 100000000 this may take couple minutes. __
_______________ Bigger limit consume more and more time. _______________
________________________________________________________________________
* - PRIME, n - natural number
integers sum qty
*2,*3,*5,*7, 17 4,
*11, *13, *17, *19, 60, 4,
n21, *23, n27, *29, 52, 2,
*31, n33, *37, n39, 68, 2,
*41, *43, *47, n49, 131, 3,
n51, *53, n57, *59, 112, 2,
*61, n63, *67, n69, 128, 2,
*71, *73, n77, *79, 223, 3,
n81, *83, n87, *89, 172, 2,
n91, n93, *97, n99, 97, 1,
*101, *103, *107, *109, 420, 4,
n111, *113, n117, n119, 113, 1,
n121, n123, *127, n129, 127, 1,
*131, n133, *137, *139, 407, 3,
n141, n143, n147, *149, 149, 1,
*151, n153, *157, n159, 308, 2,
n161, *163, *167, n169, 330, 2,
n171, *173, n177, *179, 352, 2,
*181, n183, n187, n189, 181, 1,
*191, *193, *197, *199, 780, 4,
n201, n203, n207, n209, 0, 0,
*211, n213, n217, n219, 211, 1,
n221, *223, *227, *229, 679, 3,
n231, *233, n237, *239, 472, 2,
*241, n243, n247, n249, 241, 1,
*251, n253, *257, n259, 508, 2,
n261, *263, n267, *269, 532, 2,
*271, n273, *277, n279, 548, 2,
*281, *283, n287, n289, 564, 2,
n291, *293, n297, n299, 293, 1,
n301, n303, *307, n309, 307, 1,
*311, *313, *317, n319, 941, 3,
n321, n323, n327, n329, 0, 0,
*331, n333, *337, n339, 668, 2,
n341, n343, *347, *349, 696, 2,
n351, *353, n357, *359, 712, 2,
n361, n363, *367, n369, 367, 1,
n371, *373, n377, *379, 752, 2,
n381, *383, n387, *389, 772, 2,
n391, n393, *397, n399, 397, 1,
*401, n403, n407, *409, 810, 2,
n411, n413, n417, *419, 419, 1,
*421, n423, n427, n429, 421, 1,
*431, *433, n437, *439, 1303, 3,
n441, *443, n447, *449, 892, 2,
n451, n453, *457, n459, 457, 1,
*461, *463, *467, n469, 1391, 3,
n471, n473, n477, *479, 479, 1,
n481, n483, *487, n489, 487, 1,
*491, n493, n497, *499, 990, 2,
n501, *503, n507, *509, 1012, 2,
n511, n513, n517, n519, 0, 0,
*521, *523, n527, n529, 1044, 2,
n531, n533, n537, n539, 0, 0,
*541, n543, *547, n549, 1088, 2,
n551, n553, *557, n559, 557, 1,
n561, *563, n567, *569, 1132, 2,
*571, n573, *577, n579, 1148, 2,
n581, n583, *587, n589, 587, 1,
n591, *593, n597, *599, 1192, 2,
*601, n603, *607, n609, 1208, 2,
n611, *613, *617, *619, 1849, 3,
n621, n623, n627, n629, 0, 0,
*631, n633, n637, n639, 631, 1,
*641, *643, *647, n649, 1931, 3,
n651, *653, n657, *659, 1312, 2,
*661, n663, n667, n669, 661, 1,
n671, *673, *677, n679, 1350, 2,
n681, *683, n687, n689, 683, 1,
*691, n693, n697, n699, 691, 1,
*701, n703, n707, *709, 1410, 2,
n711, n713, n717, *719, 719, 1,
n721, n723, *727, n729, 727, 1,
n731, *733, n737, *739, 1472, 2,
n741, *743, n747, n749, 743, 1,
*751, n753, *757, n759, 1508, 2,
*761, n763, n767, *769, 1530, 2,
n771, *773, n777, n779, 773, 1,
n781, n783, *787, n789, 787, 1,
n791, n793, *797, n799, 797, 1,
n801, n803, n807, *809, 809, 1,
*811, n813, n817, n819, 811, 1,
*821, *823, *827, *829, 3300, 4,
n831, n833, n837, *839, 839, 1,
n841, n843, n847, n849, 0, 0,
n851, *853, *857, *859, 2569, 3,
n861, *863, n867, n869, 863, 1,
n871, n873, *877, n879, 877, 1,
*881, *883, *887, n889, 2651, 3,
n891, n893, n897, n899, 0, 0,
n901, n903, *907, n909, 907, 1,
*911, n913, n917, *919, 1830, 2,
n921, n923, n927, *929, 929, 1,
n931, n933, *937, n939, 937, 1,
*941, n943, *947, n949, 1888, 2,
n951, *953, n957, n959, 953, 1,
n961, n963, *967, n969, 967, 1,
*971, n973, *977, n979, 1948, 2,
n981, *983, n987, n989, 983, 1,
*991, n993, *997, n999, 1988, 2,
Total primes quantity between 1 and 1000 is equal to: 168
Your calculations took 0.000 seconds to run.Warto potestować. Wystarczy zmienić jedną linijkę i można porównać prędkość z klasyczną wersją algorytmu, który jest w funkcji wyżej.
Jeszcze nie robiłem testów porównawczych co do szybkości z sitem Eratotenesa, ale mam zamiar.
Na moim PC AMD Ryzen 5 3600 6-Core Processor liczby pierwsze z przedziału 1 do 10 000 000 zlicza w czasie 4.6 sekundy.
Oto końcówka wyników:
Kod: Zaznacz cały
n9999711, *9999713, n9999717, n9999719, 9999713, 1,
n9999721, n9999723, n9999727, n9999729, 0, 0,
n9999731, n9999733, n9999737, *9999739, 9999739, 1,
n9999741, n9999743, n9999747, *9999749, 9999749, 1,
n9999751, n9999753, n9999757, n9999759, 0, 0,
*9999761, n9999763, n9999767, n9999769, 9999761, 1,
n9999771, n9999773, n9999777, n9999779, 0, 0,
n9999781, n9999783, n9999787, n9999789, 0, 0,
n9999791, n9999793, n9999797, n9999799, 0, 0,
n9999801, n9999803, n9999807, n9999809, 0, 0,
n9999811, n9999813, n9999817, n9999819, 0, 0,
n9999821, *9999823, n9999827, n9999829, 9999823, 1,
n9999831, n9999833, n9999837, n9999839, 0, 0,
n9999841, n9999843, n9999847, n9999849, 0, 0,
n9999851, n9999853, n9999857, n9999859, 0, 0,
n9999861, *9999863, n9999867, n9999869, 9999863, 1,
n9999871, n9999873, *9999877, n9999879, 9999877, 1,
n9999881, *9999883, n9999887, *9999889, 19999772, 2,
n9999891, n9999893, n9999897, n9999899, 0, 0,
*9999901, n9999903, *9999907, n9999909, 19999808, 2,
n9999911, n9999913, n9999917, n9999919, 0, 0,
n9999921, n9999923, n9999927, *9999929, 9999929, 1,
*9999931, n9999933, *9999937, n9999939, 19999868, 2,
n9999941, *9999943, n9999947, n9999949, 9999943, 1,
n9999951, n9999953, n9999957, n9999959, 0, 0,
n9999961, n9999963, n9999967, n9999969, 0, 0,
*9999971, *9999973, n9999977, n9999979, 19999944, 2,
n9999981, n9999983, n9999987, n9999989, 0, 0,
*9999991, n9999993, n9999997, n9999999, 9999991, 1,
Total primes quantity between 1 and 10000000 is equal to: 664579:
Your calculations took 4.603 seconds to run.W sposób klasyczny z funkcją is_this_prime_number() liczył wynik dla tego przedziału do 10 000 000 przez ponad 5748 sekund.
To na wstępie wszystko.
Co sądzicie o tym algorytmie?
Dzięĸuję.
