列出给定大小的单元组元素的最快方法是什么？

Question

有几种快速算法可以计算直到给定数字n的质数。但是，在C中列出所有相对质数r到某个数字n的最快实现是什么呢？也就是说，在C中尽可能有效地找到具有n个元素的乘法群的所有元素。特别是，我对n是原数的情况感兴趣。

N原始数与阶乘相似，不同之处在于只有质数相乘，其他所有数字都被忽略。所以，举个例子，12primorial就是12#=11*7*5*3*2。

我目前的实现非常幼稚。我将前3组硬编码为数组，并使用这些数组创建更大的数组。有没有更快的东西？

#include "stdafx.h"
#include <stdio.h>      /* printf, fgets */
#include <stdlib.h>     /* atoi */
#include <math.h>


int IsPrime(unsigned int number) 
{
    if (number <= 1) return 0; // zero and one are not prime

    unsigned int i;
    unsigned int max=sqrt(number)+.5;

    for (i = 2; i<= max; i++) 
    {
        if (number % i == 0) return 0;
    }

    return 1;
}

unsigned long long primorial( int Primes[], int size)
{
    unsigned long long answer = 1;

    for (int k = 0;k < size;k++)
    {
        answer *= Primes[k];
    }

    return answer;
}

unsigned long long EulerPhi(int Primes[], int size)
{
    unsigned long long answer = 1;

    for (int k = 0;k < size;k++)
    {
        answer *= Primes[k]-1;
    }

    return answer;
}


int gcd( unsigned long long a,  unsigned long long b)
{
    while (b != 0)
    {
        a %= b;
        a ^= b;
        b ^= a;
        a ^= b;
    }


    //Return whethere a is relatively prime to b
    if (a > 1)
    {
        return false;
    }

    return true;
}

void gen( unsigned long long *Gx, unsigned int primor, int *G3)
{
    //Get the magic numbers
    register int Blocks = 30;    //5 primorial=30.
    unsigned long long indexTracker = 0;

    //Find  elements using G3
    for (unsigned long long offset = 0; offset < primor; offset+=Blocks)
    {
        for (int j = 0; j < 8;j++)    //The 8 comes from EulerPhi(2*3*5=30)
        {
            if (gcd(offset + G3[j], primor))
            {
                Gx[indexTracker] = offset + G3[j];
                indexTracker++;
            }
        }
    }


}



int main(int argc, char **argv)
{
    //Hardcoded values
    int G1[] = {1};
    int G2[] = {1,5};
    int G3[] = {1,7,11,13,17,19,23,29};

    //Lazy input checking. The world might come to an end 
    //when unexpected parameters given. Its okey, we will live.
    if (argc <= 1) {
        printf("Nothing done.");
        return 0;
    }

    //Convert argument to integer
    unsigned int N = atoi(argv[1]);

    //Known values
    if (N <= 2 ) 
    {
        printf("{1}");
        return 0;
    }
    else if (N<=4)
    {
        printf("{1,5}");
        return 0;
    }
    else if (N <=6)
    {
        printf("{1,7,11,13,17,19,23,29}");
        return 0;
    }

    //Hardcoded for simplicity, also this primorial is ginarmous as it is. 
    int Primes[50] = {0};
    int counter = 0;

    //Find all primes less than N.
    for (int a = 2; a <= N; a++)
    {
        if (IsPrime(a))
        {
            Primes[counter] = a;
            printf("\n  Prime: : %i \n", a);
            counter++;
        }
    }

    //Get the group size
    unsigned long long MAXELEMENT = primorial(Primes, counter);
    unsigned long long Gsize = EulerPhi(Primes, counter);

    printf("\n  GSize: %llu \n", Gsize);
    printf("\n  GSize: %llu \n", Gsize);

    //Create the list to hold the values
    unsigned long long  *GROUP = (unsigned long long *) calloc(Gsize, sizeof(unsigned long long));

    //Populate the list
    gen( GROUP, MAXELEMENT, G3);

    //Print values
    printf("{");
    for (unsigned long long k = 0; k < Gsize;k++)
    {
        printf("%llu,", GROUP[k]);
    }
    printf("}");


    return 0;
}

Answer 1

如果你正在寻找一个更快的质数检查，这里有一个相当快，并且消除了对计算密集型函数(例如sqrt等)的所有调用。

int isprime (int v)
{
    int i;

    if (v < 0) v = -v;                          /* insure v non-negative */
    if (v < 2 || !((unsigned)v & 1))    /* 0, 1 + even > 2 are not prime */
        return 0;

    for (i = 2; i * i <= v; i++)
        if (v % i == 0)
            return 0;

    return 1;
}

(注意：如果要查找大于标准type范围的数字，可以根据需要调整int。)

试一试，让我知道它与您当前使用的一次相比如何。