Totient function

Question

Czesc, napisalem program ktory na wejsciu ma liczbe n a zwraca tablice ktora na i-tym miejscu ma liczbe liczb wzglednie pierwszych z i oraz mniejszych od i. Program dziala poprawnie dla  liczb mniejszych od okolo 1000. dla wiekszych daje w ogole return -1. Domyslam sie ze gdzies przekraczam jakis zakres abo cos w tym stylu, tylko nie mam pojecia gdzie. tutaj jest kodzik gdyby ktos cos zauwazyl bede wdzieczny za pomoc

#include<stdio.h>



void mnozenie(int p,int n,int A[])
{

    int B[n+1],k;//to bedzie taka pomocnicza tablica, rozlaczna z A[] ktora pozniej polaczymy z A[]

    for(int i=0;i<n+1;i++)
{
    B[i]=0; // tutaj B[i]=0
}


    for (int i=1;i<n+1;i++)
    {
        if (A[i]!=0)
        {
            if(i*p<n+1)
                B[i*p]=A[i]*(p-1);
                k=i*p;
            while(k*p<n+1)
            {
                B[k*p]=B[k]*p;
                k=k*p;

            }
        }
    }

    for (int i=1;i<n+1;i++)
    {
        if (B[i]!=0)
            A[i]=B[i];
    }
}






int main()
{
    int p=2; //po liczbach pierwszych
    int j=2; //zmienna na domnażanie

    int n;
    scanf("%d",&n);
    int k=0; // to nam policzy ile jest primsow mniejszych od n
int A[n+1]; // tu sa wszystkie liczby od 0 do n, pozniej liczby pierwsze i zera

// tutaj A[i]=0

for(int i=0;i<n+1;i++)
{
    A[i]=i; // tutaj A[i]=n
}
while(p*p<n+2)// should be sqrt
{
    if (A[p]!=0)
    {
        j=2;
        while(p*j<n+2)
        {
            A[p*j]=0;
            j++;
        }
    }
    p++;
}
for(int i=0;i<n+1;i++)
{
   // printf("%d ",A[i]);
}

for(int i=0;i<n+1;i++)
{
    if(A[i]!=0)
        k++;
}
//printf("%d ",k);




int P[k-1]; //z samymi liczbami pierwszymi BEZ JEDYNKI I DLATEGO k-1
int l=0;
for(int i=2;i<n+1;i++)
{
    if(A[i]!=0)
   {

    P[l]=A[i];
    l++;
   }

}
//for(int i=0;i<k-1;i++)
//{
  //  printf("%d ",P[i]);
//}

// DOBRA TABLICA P[k-1] TO TABLICA Z LICZBAMI PIERWSZYMI MNIEJSZYMI OD n to mogla by byc funkcja ale tak tez chyba ok




    int C[n+1];
    for(int i=0;i<n+1;i++)
{
    C[i]=0;
}
C[1]=1;

for (int i=0;i<k-1;i++)
{
    mnozenie(P[i],n,C);
}

for(int i=0;i<n+1;i++)
{
    printf("%d ",C[i]);
}



    return 0;

}

 

Answer 1

Hej,

Rzuć okiem na linię 23 (tu 8).

    for (int i=1;i<n+1;i++)
    {
        if (A[i]!=0)
        {
            if(i*p<n+1)
                B[i*p]=A[i]*(p-1);
                k=i*p;
            while(k*p<n+1)
            {
                B[k*p]=B[k]*p;
                k=k*p;
             }
        }
    }

• dla 1291
  • k:1662808, p:1291, k*p:2146685128
  • k:1664099, p:1291, k*p:-2146615487

Powodzenia!

PS.
Swoją drogą, czy to celowa podpucha, że instrukcja warunkowa z linii 20 (tu 5) nie ma klamer i obie linie wcięte są na tym samym poziomie?

Comments

Dziękuję :)