Tìm số nguyên tố bằng phương pháp sàng Eratosfen!

[thaiboss]

Cho số tự nhiên n(n>=2).Hãy sử dụng phương pháp sàng Eratosfen để tìm tất cả các số nguyên tố bé hơn n.Viết tất cả các số nguyên tố từ 2 đến n,số nguyên tố đầu tiên là 2.Đánh dấu số 2 và gạch bỏ các số là bội của 2.Số nguyên tố đầu tiên nguyên tố còn lại tiếp theo là 3.Đánh dấu số 3 và gạch bỏ các số là bội của 3.Tiếp tục đến 5,7,11...Cho đến khi ko còn số nào để xét,những số được đánh dấu là số nguyên tố.Viết chương trình giải bài toán trên

Ai bit thuật toán bài này như thế nào chỉ mình với,bài này dùng mảng hay là gì? Thanks các bạn nhìu....

[dark_baron]

Bạn vào đây để xem thêm về sàng Eratosthene
Đây là code mình chuyển sang C++

/*Eratosthene*/
#include <iostream.h>
#include <math.h>
using namespace std;

const int TRUE=1;
const int FALSE=0;

int main()
{
    int n;
    cout<<"Enter n = ";
    cin>>n;
    int *prime;
    prime = new int [n+1];
    int i;
    for ( i=1; i <= n; i++) prime[i]=TRUE;
    prime[1]=FALSE;
    int k=0,m=sqrt(n),j;
    while (k<m)
    {
        i=k+1;                    
        while (prime[i]==FALSE) i++;
        k=i;
        j=2;
        prime[k]=TRUE;
        while (k*j<=n)
        {
            prime[k*j]= FALSE;
            j++;
        }
    }
    for (i=1; i <= n; i++)
        if (prime[i]==TRUE) cout<<"   "<<i;
    delete[] prime;
}

[AlexF]

Cho số tự nhiên n(n>=2).Hãy sử dụng phương pháp sàng Eratosfen để tìm tất cả các số nguyên tố bé hơn n.Viết tất cả các số nguyên tố từ 2 đến n,số nguyên tố đầu tiên là 2.Đánh dấu số 2 và gạch bỏ các số là bội của 2.Số nguyên tố đầu tiên nguyên tố còn lại tiếp theo là 3.Đánh dấu số 3 và gạch bỏ các số là bội của 3.Tiếp tục đến 5,7,11...Cho đến khi ko còn số nào để xét,những số được đánh dấu là số nguyên tố.Viết chương trình giải bài toán trên

Ai bit thuật toán bài này như thế nào chỉ mình với,bài này dùng mảng hay là gì? Thanks các bạn nhìu...

trước hết xin hỏi cậu là cậu muốn làm bài tìm số nguyên tố theo cách này hay chỉ đơn giản là muốn làm tìm số nguyên tố
cách này theo mình nghĩ thì không khó,cậu chỉ việc viết 1 hàm xóa các giá trị là bội của số mà cậu đang xét ( số chạy i)
nhưng cách này nếu triển khai thì quá dài và tốn thời gian,mình có nhiểu cách ngắn hơn

[developer]

Ai bit thuật toán bài này như thế nào chỉ mình với,bài này dùng mảng hay là gì? Thanks các bạn nhìu....

Thực ra cũng không phải là kĩ thuật xóa gì đâu, là kĩ thuật đánh dấu mảng thôi
Vì mình không biết C++ nên góp một cách bằng C, hình như là giống cách trên

#include <stdio.h>#include <stdlib.h> void Eratosten(int n){  int i,j;  int *a;  a=(int *)malloc((n+1)*sizeof(int));  if(a==NULL){    printf("There isn't enough memory\n");    return ;  }  for(a[0]=a[1]=0,i=2;i<n+1;i++)    a[i]=1;  for(i=0;i<n+1;i++)    if(a[i]==1){      j=2;      while(i*j<n+1){    a[i*j]=0;    j++;      }    }  for(i=0;i<n+1;i++)    if(a[i]==1)      printf("%d  ",i);  printf("\n");  free(a);} main(){  int n;  printf("Nhap n: ");  scanf("%d",&n);  printf("Cac so nguyen to nho hon hoac bang %d la:\n",n);  Eratosthen(n);}

[rox_rook]

It's simple :

#include <iostream>#include <vector> int main () {    int sieve_size;    std::cout << "Input a number : ";    std::cin >> sieve_size;     std::vector< int > sieve( sieve_size, 1 );       for( int i = 2; i * i < sieve_size; ++i ) {        if( sieve[ i ] ) {            for( int j = i + i; j < sieve_size; j += i )                  sieve[ j ] = 0;         }    }     for( int j = 2; j < sieve_size; ++j )        if( sieve[ j ] )            std::cout << j << " ";     return 0;}

[zzzvazzz]

thuật toán thì mình biết nhiều cái ngắn hơn, nhưng mà với số cực lớn thì cách liệt kê của bạn là nhanh nhất

[huudien1993]

Có cách nào không dùng mảng và không dùng con trỏ không ạ, chỉ dùng các câu lệnh điều khiển thôi ạ

[prog10]

Có cách nào không dùng mảng và không dùng con trỏ không ạ, chỉ dùng các câu lệnh điều khiển thôi ạ

(Reply cho riêng bạn) Có, nhưng mình ko khuyến khích (vì nó rùa)