Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 12 kết quả

Đề tài: Thuật toán tìm số nguyên tố thõa điều kiện cho trước

  1. #1
    Ngày gia nhập
    03 2009
    Nơi ở
    TP Hồ Chí Minh
    Bài viết
    11

    Mặc định Thuật toán tìm số nguyên tố thõa điều kiện cho trước

    Mình muốn hỏi thuật toán tìm số nguyên tố nhỏ hơn và gần nhất của 1 số cho trước thì làm thế nào?
    VD số cho trước là 100 thì sẽ xuất ra kết quả là 97.

  2. #2
    Ngày gia nhập
    01 2009
    Nơi ở
    Hà Nội
    Bài viết
    205

    - Trước hết lập 1 hàm kiểm tra nguyên tố (cái này chắc bạn biết rồi chứ ).

    - Cho 2 vòng lặp vô tận (có thể dùng while()), duyệt theo 2 phía :
    + Vòng 1:100 trở xuống
    + Vòng 2: 100 trở lên
    Yêu cầu: kiểm tra số nguyên tố ở mỗi vòng, nếu có số nguyên tố nào thỏa mãn thì nhẩy ra khỏi vòng lặp luôn.

    - Chỉ việc so sánh xem trong 2 số nguyên tố vửa tìm được (1 lớn hơn. 1 nhỏ hơn) cái nào gần 100 hơn (100 là con số mang tính hình tượng).
    Vậy là xong.

  3. #3
    Ngày gia nhập
    11 2008
    Bài viết
    73

    Đơn giản như sau : Giả sử số nhập vào cho trước là n .
    1 - Viết một hàm KiemTra(m) : dùng để kiểm tra xem số m có phải là số nguyên tố không
    2 - Dùng một vòng for.
    for (i=n -> 2)
    if KiemTra(i) = true
    {
    - In ra số m
    - Break (Thoát khỏi vòng lặp)
    }

  4. #4
    Ngày gia nhập
    03 2009
    Nơi ở
    TP Hồ Chí Minh
    Bài viết
    11

    Code:
    #include <iostream.h>
    int main()
    {
    	int n,i,j,m,l;
    	j = 1;
    	cin >>m;
    	for (l=2;l<m;l++)
    	{n=m-1;
    	if (n==1) j=0; 
    	for(i=2;i<=n/2;i++)
    	if(n % i == 0)	{j=0; break;}
    	else j=1;
    	if (j == 1) {cout<<n; break;}
    	}
    	return 0;
    
    }
    Trên đó là code của mình, mà thấy chỉ thõa vài trường hợp àh. Mình ko biết sai chỗ nào :P, xin chỉ giáo . Mình vẫn chưa học hàm, mới học đến vòng lặp àh.

  5. #5
    Ngày gia nhập
    02 2008
    Nơi ở
    Việt Nam
    Bài viết
    577

    Mới học thì code cho chuẩn môt chút nhé!

    C++ Code:
    1. #include <iostream>
    2. #include <cmath>
    3. using namespace std;
    4.  
    5. int main()
    6. {
    7.      int m,i,j;
    8.      cout << " - Enter m = "; cin >> m;
    9.      while(1)
    10.      {
    11.           j = 1;
    12.           if (m==1) j=0;
    13.           for(i=2;i<=sqrt(m);i++)
    14.                if(m % i == 0) {j=0; break;}
    15.           if (j == 1) {cout << " - Result: " << m; break;}
    16.           m--;
    17.      }
    18.      return 0;
    19. }

    @edited.
    Đã được chỉnh sửa lần cuối bởi QuangHoang : 29-03-2009 lúc 10:29 AM.

  6. #6
    Ngày gia nhập
    03 2009
    Nơi ở
    TP Hồ Chí Minh
    Bài viết
    11

    Mặc định Thuật toán tìm số nguyên tố thõa điều kiện cho trước

    ^^. Thanks. Nhưng hình như vẫn có trường hợp ko thõa :P. Vd mình nhập 9 ~> kq là 3, nhập 3 trả về 3 (nhưng mình muốn kết quả là số nguyên tố nhỏ hơn gần nó nhất). Mà cái "using namespace std;" là sao ?
    Đã được chỉnh sửa lần cuối bởi dk0705 : 29-03-2009 lúc 10:29 AM.

  7. #7
    Ngày gia nhập
    02 2008
    Nơi ở
    Việt Nam
    Bài viết
    577

    Đã edit lại chút do không xóa hết biến n.
    Mà cái "using namespace std;" là sao ?
    Đó là C++ chuẩn ANSI đó bạn. Chịu khó đọc bài trên diễn đàn, sẽ thấy những người có kinh nghiệm sẽ code C++ như vậy.

    Mới học thì code cho chuẩn môt chút nhé!
    Cái mình muốn ở đầy là chuẩn C++ mới.

  8. #8
    Ngày gia nhập
    03 2009
    Nơi ở
    TP Hồ Chí Minh
    Bài viết
    11

    Thanks bạn nhiều. Mình sẽ tìm hiểu thêm
    Đã được chỉnh sửa lần cuối bởi dk0705 : 29-03-2009 lúc 10:44 AM.

  9. #9
    Ngày gia nhập
    11 2008
    Bài viết
    203

    Code này xem ra "ngu" hơn,nhưng có thể bạn sẽ hiểu:
    Ý tưởng: Cho một biến chạy từ n xuống 2, thấy chú nào là nguyên tố đầu tiên sẽ in chú đó ra và kết thúc vòng lặp ngay.
    Code:
    #include<conio.h>
    #include<stdio.h>
    #include<math.h>
    
    int main()
    {
    	int n=0;//TO THICH GAN NHU VAY DAY!
    	bool bien_kt_so_ngto_lonnhat=false;
    	printf("Nhap vao mot con so: ");scanf("%d",&n);
    	do
    	{
    		
    		/*int bienchay=2,canbachai=0,phandu=0;
    		canbachai=int(sqrt(n));
    		bool ktnguyento=true;
    		do
    		{
    			phandu=n%bienchay;
    			if(phandu==0&&(n!=2))
    			   ktnguyento=false;
    		}while(ktnguyento==true&&bienchay++<=canbachai);*/
    		if(ktnguyento)
    		   bien_kt_so_ngto_lonnhat=true;
    	 }while(n-->2&&bien_kt_so_ngto_lonnhat==false);
    	 printf("%d",n+1);
    	getch();	
    }
    Cái đoạn trong /*....* /để kiểm tra xem n có là nguyên tố hay không.
    Có 2 dòng while:
    Dòng while lớn nhất dùng để cho biến chạy từ n xuống 2 + kiểm tra xem có được thoát chưa (Điều kiện thoát là: n là số nguyên tố);
    Dòng while ở trong dùng để kiểm tra xem n có là số nguyên tố chưa.
    Ví dụ:
    n=100;
    Dòng while ở trong sẽ kiểm tra xem n có là số nguyên tố không? Thuật toán như sau:
    -Cho bienchay chạy từ n đến căn bậc hai của n (hàm sqrt(n)), vì sqrt trả về float nên phải ép kiểu cho nó trả về int;
    -Nếu n chia hết cho bất kì số nào thuộc khoảng từ 2 đến canbachai của n thì nó không là nguyên tố, ngược lại thì nó là số nguyên tố.

    100 không là số nguyên tố.
    Dòng while lớn thực hiện việc giảm n xuống còn 99;
    Dòng while ở trong lại kiểm tra xem 99 có là nguyên tố không?
    ...............................
    ...............................
    97: Dòng while ở trong kiểm tra và xác thực nó là số nguyên tố.
    bien_kt_so_ngto_lonnhat=true;//biến này được bật lên để catch số nguyên tố lớn đầu tiên.
    Trở lại dòng while lớn, điều kiện không thỏa.
    Kết thúc dòng while lớn.
    printf(n+1)//Vì lúc nãy nó đã giảm n=n-1, nhưng n mới là số nguyên tố. Xuống tới đây phải cộng 1 trở lại thì nó mới được kết quả chính xác.
    Còn nếu muốn in tất cả các số nguyên tố nhỏ hơn n thì bỏ đi một số bước và một số biến là được.
    Code:
    #include<conio.h>
    #include<stdio.h>
    #include<math.h>
    
    int main()
    {
    	int n=0;//TO THICH GAN NHU VAY DAY!
    	bool bien_kt_so_ngto_lonnhat=false;
    	printf("Nhap vao mot con so: ");scanf("%d",&n);
    
    	do
    	{
    		
    		int bienchay=2,canbachai=0,phandu=0;
    		canbachai=int(sqrt(n));
    		bool ktnguyento=true;
    		do
    		{
    			phandu=n%bienchay;
    			if(phandu==0&&(n!=2))
    			   ktnguyento=false;
    		}while(ktnguyento==true&&bienchay++<=canbachai);
    		if(ktnguyento)
    		   printf("%d\n",n);
    	 }while(n-->2);
    	 
    	getch();	
    }
    Trong chương trình có sử dụng hàm sqrt() nên phải khai báo include<math.h> để thực hiện các hàm toán học.
    Đã được chỉnh sửa lần cuối bởi Loveanygirls : 29-03-2009 lúc 12:08 PM.
    Tôi tin rằng: giải thuật thì có thể tìm trong hàng trăm GB ebook, hoặc Google nhưng code chạy thì chưa chắc! Hãy post code để chứng tỏ giải thuật của bạn là đúng!
    Giải thuật là bản thiết kế của ngôi nhà, code là phần xây dựng. Nếu chỉ xây nhà trên giấy thì ta sống chả khác nào người nguyên thủy.

  10. #10
    Ngày gia nhập
    11 2008
    Bài viết
    73

    Bạn xem đoạn code này có thỏa mãn yêu cầu của bạn không>
    Code:
    // Check_NTo.cpp : Defines the entry point for the console application.
    //
    
    #include "stdafx.h"
    #include <iostream>
    using std::cout;
    using std::cin;
    using std::endl;
    bool Check(int so);
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int n;
    	cout << "Nhap so N (n>2): " ;
    	cin >> n;
    	for (int i=n;i--;i>=2)
    	{
    		if (Check(i)== true)
    		{
    			cout << "So nguyen to gan nhat voi N la : " << i << endl;
    			break;
    		}
    	}
    	return 0;
    }
    bool Check(int so)
    {
    	bool Flag = true;
    	if (so==2)return Flag;
    	else 
    	for (int i=2;i<=so;i++)
    		if ((so !=i ) && (so % i == 0)) 
    		{
    			Flag = false;
    			break;
    		}
    	return Flag;
    }

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. thuật toán số nguyên tố????
    Gửi bởi anhtbok trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 9
    Bài viết cuối: 30-03-2012, 10:33 AM
  3. Bài tập C kiểm tra dãy số thõa mãn tính chất của cấp số nhân hay số cộng hay không?; tính tổng s
    Gửi bởi luunguyen 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-06-2011, 03:19 PM
  4. 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
  5. Hàng đợi | Thuật toán in đảo số nguyên n
    Gửi bởi hoangchauhamy trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 18-05-2009, 08:37 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