Từ 1 tới 8 trên tổng số 8 kết quả

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

  1. #1
    Ngày gia nhập
    04 2008
    Bài viết
    12

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

    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....

  2. #2
    Ngày gia nhập
    07 2008
    Bài viết
    4

    Bạn vào đây để xem thêm về sàng Eratosthene
    Đây là code mình chuyển sang C++
    Code:
    /*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;
    }

  3. #3
    Ngày gia nhập
    02 2008
    Bài viết
    1,009

    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

  4. #4
    Ngày gia nhập
    02 2008
    Nơi ở
    AYS 107
    Bài viết
    41

    Trích dẫn Nguyên bản được gửi bởi thaiboss Xem bài viết
    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

    C Code:
    1. #include <stdio.h>
    2. #include <stdlib.h>
    3.  
    4. void Eratosten(int n)
    5. {
    6.   int i,j;
    7.   int *a;
    8.   a=(int *)malloc((n+1)*sizeof(int));
    9.   if(a==NULL){
    10.     printf("There isn't enough memory\n");
    11.     return ;
    12.   }
    13.   for(a[0]=a[1]=0,i=2;i<n+1;i++)
    14.     a[i]=1;
    15.   for(i=0;i<n+1;i++)
    16.     if(a[i]==1){
    17.       j=2;
    18.       while(i*j<n+1){
    19.     a[i*j]=0;
    20.     j++;
    21.       }
    22.     }
    23.   for(i=0;i<n+1;i++)
    24.     if(a[i]==1)
    25.       printf("%d  ",i);
    26.   printf("\n");
    27.   free(a);
    28. }
    29.  
    30. main()
    31. {
    32.   int n;
    33.   printf("Nhap n: ");
    34.   scanf("%d",&n);
    35.   printf("Cac so nguyen to nho hon hoac bang %d la:\n",n);
    36.   Eratosthen(n);
    37. }
    I don't wanna waste another day

  5. #5
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    It's simple :
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3.  
    4. int main ()
    5. {
    6.     int sieve_size;
    7.     std::cout << "Input a number : ";
    8.     std::cin >> sieve_size;
    9.  
    10.     std::vector< int > sieve( sieve_size, 1 );
    11.  
    12.     for( int i = 2; i * i < sieve_size; ++i ) {
    13.         if( sieve[ i ] ) {
    14.             for( int j = i + i; j < sieve_size; j += i )  
    15.                 sieve[ j ] = 0;
    16.         }
    17.     }
    18.  
    19.     for( int j = 2; j < sieve_size; ++j )
    20.         if( sieve[ j ] )
    21.             std::cout << j << " ";
    22.  
    23.     return 0;
    24. }

  6. #6
    Ngày gia nhập
    08 2012
    Bài viết
    1

    Mặc định Hay

    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

  7. #7
    Ngày gia nhập
    01 2013
    Bài viết
    8

    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 ạ

  8. #8
    Ngày gia nhập
    01 2013
    Bài viết
    1,476

    Trích dẫn Nguyên bản được gửi bởi huudien1993 Xem bài viết
    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)
    Đã được chỉnh sửa lần cuối bởi prog10 : 19-08-2014 lúc 09:13 AM.

Các đề tài tương tự

  1. Bài tập C giải thuật nhập vào số nguyên n in ra n số nguyên tố đầu tiên?
    Gửi bởi LTC trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 48
    Bài viết cuối: 25-04-2013, 07:40 PM
  2. Viết chương trình nhập số nguyên dương n, liệt kê n số nguyên tố đầu tiên.
    Gửi bởi maiit trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 11
    Bài viết cuối: 19-06-2011, 01:05 PM
  3. Game Viết chương trình nhập số nguyên dương n, liệt kê n số nguyên tố đầu tiên trên C#?
    Gửi bởi maiit trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 18
    Bài viết cuối: 08-06-2011, 11:12 PM
  4. Bài tập C++ chương trình đổi 1 số nguyên trong hệ thập phân sang hệ fibo và cộng 2 số nguyên được
    Gửi bởi nghiapro512 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 23-01-2011, 02:14 PM
  5. Lập trình C xin code cài đặt thuật toán sàng nguyên tố để liệt kê các số nguyên tố 2->480000
    Gửi bởi ngocdung_088 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 23
    Bài viết cuối: 06-12-2010, 11:53 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn