Program prime sieve

Added by Lasguido Eleazar over 8 years ago

/*
  generate prime
  sieve of eratosthenes
  author lasguido
  date 10-12-2010
  v 1.1
*/

#include <stdio.h>
#define MAXN 3000000

int flag[MAXN];
long long prime[MAXN];
int size;

void generate_prime(){
    int i, j;
    //memset(flag, 0, sizeof(flag)); //karena di kernel operasi memset menimbulkan warning
    for (i = 0 ; i < MAXN ; i ++) flag[i] = 0;
    size = 0;
    for (i = 2 ; i < MAXN ; i ++){
        if (flag[i]==0){
            prime[size++] = i;
            for (j = i+i ; j < MAXN ; j += i) flag[j] = 1;
        }
    }
}

long long prime_call(int idx){
     if (idx > 0 && idx <= size)
         return prime[idx-1];
     else
         return -1;
}

int main(){
    int in;
    generate_prime();
    while(scanf("%d", &in)!=EOF){
        printf("%lld\n", prime_call(in));
    }
    return 0;
}


Replies (7)

RE: Program prime sieve - Added by 0806457810 RAMANDA over 8 years ago

Program ini belum bisa jalan di system call ya??

RE: Program prime sieve - Added by 0806457602 HARWIN over 8 years ago

Do, jadi yang harus dilakukan itu men"translate" code di atas sedemikian sehingga bisa "dimengerti" oleh kernel ya?

RE: Program prime sieve - Added by Lasguido Eleazar over 8 years ago

@ramanda : belum, harus dimasukkan dulu ke sistem call
@harwin : xD

RE: Program prime sieve - Added by Gladhi Guarddin adin over 8 years ago

kalau kalian mau belajar programming kernel, ada 2 cara:

  1. cari resource nya di internet
  2. buka source code salah satu modul di source code kernel

RE: Program prime sieve - Added by Lasguido Eleazar over 8 years ago

/**
    Length prime - extended shieve algorithm
    @author lasguido
    version 1.0
    c++ version
*/

#include <iostream>
#include <vector>
#include <cmath>
#define MAXN 500000
using namespace std;

long long m, n;
vector<long long> prime;
bool temp[MAXN];
bool ans[100005];
int len;

int main()
{
    //generate prime
    for (int i = 0 ; i < MAXN ; i ++) temp[i] = true;
    for (int i = 2 ; i < MAXN ; i ++){
        if (temp[i]){
            prime.push_back(i);
            for (int j = i+i ; j < MAXN ; j +=i)
                temp[j] = false;
        }
    }

    //buffer prime size
    len = prime.size();

    long long ctr;
    long long square;

    //read input
    scanf("%lld %lld", &m, &n);

    //buffer length
    for (int i = 0 ; i < 100005 ; i ++) ans[i] = true;

    ctr = 0;
    square = (long long) sqrt(n);

    //compute prime
    while(ctr < len && prime[ctr]<=square){
        for (long long i = (m/prime[ctr])*prime[ctr] ; i <= n ; i +=prime[ctr]){
            if (i >=m && ans[i-m] && i!=prime[ctr]){
                ans[i-m]=false;
            }
        }
        ctr++;
    }

    for (long long i = 0 ; i <= n-m ; i ++){
        if (ans[i] && i+m!=1){
            printf("%lld\n", i+m);
        }
    }

    return 0;
}

RE: Program prime sieve - Added by Lasguido Eleazar over 8 years ago

/**
    Length prime - extended shieve algorithm
    @author lasguido
    version 1.0
    c version
*/

#include <stdio.h>
#include <math.h>
#define MAXN 500000
#define ANSBUFF 100005

long long m, n, loop;
long long prime[MAXN];
int temp[MAXN];
int ans[ANSBUFF];
int len, i, j;

int main()
{
    long long ctr;
    long long square;

    len = 0;

    //generate prime
    for (i = 0 ; i < MAXN ; i ++) temp[i] = 1;
    for (i = 2 ; i < MAXN ; i ++){
        if (temp[i]==1){
            prime[len++] = i;
            for (j = i+i ; j < MAXN ; j +=i) temp[j] = 0;
        }
    }

    //read input
    scanf("%lld %lld", &m, &n);

    //buffer length
    for (i = 0 ; i < ANSBUFF ; i ++) ans[i] = 1;

    ctr = 0;
    square = (long long) sqrt(n);

    //compute prime
    while(ctr < len && prime[ctr]<=square){
        for (loop = (m/prime[ctr])*prime[ctr] ; loop <= n ; loop +=prime[ctr]){
            if (loop >=m && ans[loop-m] && loop!=prime[ctr]){
                ans[loop-m]=0;
            }
        }
        ctr++;
    }

    //generate answer
    for (loop = 0 ; loop <= n-m ; loop++){
        if (ans[loop] && loop+m!=1){
            printf("%lld\n", loop+m);
        }
    }

    return 0;
}

(1-7/7)