質數

質數篩法

#define N 100
int isprime[N];
int prime[N],pnum;
void sieve(int n)
{
    pnum=0;
    for(int i=0;i<n;i++)
        isprime[i]=1;
    isprime[0]=isprime[1]=0;
    int sqn=sqrt(n);
    for(int i=2;i<=sqn;i++)
    {
        if(isprime[i])
        {
            prime[pnum++]=i;
            for(int j=i*i;j<n;j+=i)
                isprime[j]=0;
        }
    }
    for(int i=sqn+1;i<=n;i++)
    {
        if(isprime[i])
            prime[pnum++]=i;
    }
}

其他

int isprime[N]={1,1};
    int sqn=sqrt(N);
    for(int i=2;i<=sqn;i++)
    {
        if(!isprime[i])
        {
            for(int j=i*i;j<N;j+=i)
                isprime[j]=1;
        }
    }

int Prime[100], Pt;
void Sieve() {
 Pt = 0;
 int i, j, mark[100] = {0};
 Prime[Pt++] = 2;
 for(i = 3; i < 100; i += 2) 
 {
  if(mark[i] == 0) 
  {
   Prime[Pt++] = i;
   for(j = 3; i*j < 100; j += 2)
    mark[i*j] = 1;
  }
 }
}

質因數

#include <stdio.h>
#include <math.h>
#define M 1000
#define N 10000
int fact[M],count[M],fnum;
int prime[N],isprime[N],pnum;
void sieve()
{
    int sqn=sqrt(N);
    isprime[0]=isprime[1]=1;
    for(int i=2;i<N;i++)
    {
        if(!isprime[i])
        {
            for(int j=i+i;j<=N;j+=i)
                isprime[j]=1;
        }
    }
    pnum=0;
    for(int i=0;i<N;i++)
    {
        if(!isprime[i])
            prime[pnum++]=i;
    }
}
void factorization(int n)
{
    fnum=0;
    for(int i=0;i<pnum&&n>1;i++)
    {
        if(n%prime[i]==0)
        {
            fact[fnum]=i;
            count[fnum]=0;
            fnum++;
            while(n%prime[i]==0)
            {
                count[fnum-1]++;
                n/=prime[i];
            }
        }
    }
}
int main()
{
    sieve();
    factorization(120);
    printf("%d = \n",120);
    for(int i=0;i<fnum;i++)
        printf("%d^%d\n",prime[fact[i]],count[i]);
    return 0;
}