Как быстрее всего перечислить элементы группы единиц заданного размера?

Существует несколько быстрых алгоритмов вычисления простых чисел до заданного числа n. Но, какая самая быстрая реализация перечислить все числа r относительно простого к некоторому числу n в C? То есть найти все элементы мультипликативной группы С n элементами как можно эффективнее в C. В частности, меня интересует случай, когда n является приморским.

N primorial похож на факториал, за исключением того, что только простые числа умножаются вместе, а все другие числа игнорируются. Так, например 12 приморских было бы 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;
}

1 ответ

  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диапазона.)

    Дайте ему попробовать и дайте мне знать, как он сравнивает с один раз вы в настоящее время используете.