Mã nguồn bài toán tìm số nguyên tố bằng C

Bài này mình viết khi học môn Kỹ thuật Lập trình của thầy Hoàng Minh Sơn, để tìm N số nguyên tố đầu tiên với thuật toán tối ưu. Các bạn xem nhé, lấy làm tham khảo, ai có ý kiến ý cò gì thì cứ cho nhé :d.

Nay mở lại các email đã gửi mới tìm thấy cái này :d.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include "iostream"
#include "math.h"
using namespace std;
 
void findPrimesSequence(int N,int *primes);
int findNextPrimes(int k,int *primes);
/******************** Main function ****************** */
int main(){
	int N;
	int *primes;
	cout< <"Input the number of primes you want to find: ";
	cin>>N;
	if(N< =0) exit(1);
	cout<<endl;
	primes=new int[N] ;
	findPrimesSequence(N,primes);
	for (int i=1;i<=N;i++){
		cout.width(8);
		cout<<primes[i-1];
		if (i%9==0) cout<<endl;
	};
	delete primes;
	return 0;
}
/*************** Other functions *****************/
void findPrimesSequence(int N,int *primes){
	primes[0]=2;
	if (N>1) primes[1]=3;
	int k=2;
	while (k<n ){
		primes[k]=findNextPrimes(k-1,primes);
		k++;
		};
}
 
int findNextPrimes(int k,int *primes){
	int start=primes[k];
	while(1){
		start+=2;
		bool found=true;
		if (start%6==1||start%6==5){
			for(int i=1;i<sqrt(start);i++)
				if (start % primes[i]==0) found=false;
			if (found==true) return(start);
		};
	};
}

{ 9 comments… add one }

  • Hưng March 28, 2009, 6:09 am

    Em chưa hiểu thuật toán mà anh viết, anh có thể giải thích rõ hơn không ạ?
    trong hàm tìm số nguyên tố tiếp theo

    Thứ nhất : Nếu (1 số nguyên tố + 2) :6 dư khác 5 và 1 thì câu lệnh
    if (start%6==1||start%6==5)…….
    bị bỏ qua , và dẫn đến vòng lặp vô hạn? Hơn nữa nếu dư khac 5 và 1 thì chắc chắn không là số nguyên tố ạ?

    thứ 2 :
    primes là con trỏ tới các số nguyên tố tìm được .
    Quy tắc tìm số nguyên tố mà em biết thì đem chia thử số đó cho tất cả các số nguyên tố nhở hơn căn của nó , có nghĩa là chia đến khi primes[i] = sqrt(start) . Câu lệnh theo em là : for(int i=1;primes[i]<sqrt(start);i++) ………
    Còn trong giải thuật của anh lại chia đến khi i= sqrt( start) ????? Điều này chắc chắn sẽ dẫn đến việc con trỏ truy cập vào các vùng nhớ không kiểm soát khi số cần kiểm tra lớn và mảng các số nguyên tố ít hơn căn của của số đó

    Reply
    • ngohaibac March 28, 2009, 8:47 am

      Chào em.

      Rất vui vì em quan tâm tới bài mà anh post nhé :) , cái bài này anh copy khi anh làm từ hồi anh học đại học năm thứ 3, may mà tìm trong email. Anh đang bận nên trả lời từ từ nhé.

      Câu 1
      i = 6.m + n, nếu n khác 1 hoặc 5 thì n = 0, 2, 3, 4 thì i có chia hết cho 2 hoặc 3 không ? Nên nó là số gì em ?
      Nếu i chia 6 khác 1 hoặc 5 thì tăng start lên, kiểm tra đến khi tìm được số nguyên tố mới thì thôi, chứ không phải lặp vô hạn.

      Câu 2
      Nhận xét của em là đúng đó :), sẽ phải thay: for(int i=1;i<sqrt(start);i++) thành for(int i=1;primes[i]<sqrt(start);i++)

      Chúc em thành công.

      Reply
  • Hoàng Ngọc Minh July 24, 2009, 10:06 am

    Bài này làm đơn giản thôi mà
    Bạn làm như vậy mình thấy khó hiểu lắm
    Ctrl+F9 ~> Lỗi còn khá nhiều!

    Reply
  • vu hong quan FPT aptech October 14, 2009, 11:06 am

    hjc bai cua cac’ anh tra thuc. dung. j ca? em moi’ hoc. den con tro? cua giao’ trjnk C thj lam theo kieu dey’ de? ma co giao’ ch0 diem? 1 ak

    Reply
  • Nguyễn Duy Thành October 14, 2009, 4:42 pm

    Anh có thể cho em xin mã nguồn bài toán tìm n số nguyên tố đầu tiên được không.Em cũng đang học KT Lập Trình.Em cảm ơn!

    Reply
  • akabuki August 26, 2010, 12:24 am

    bài này sao phải dùng đến tận namespace! các hàm đệ quy cũng giải quyết gọn được mà anh

    Reply
  • le hong thai October 20, 2010, 9:32 am

    đề bài la nhâp vao 1 mang nguyên sau đo in ra các số nguyên tố.mọi ngươi xem thuật toan mình viết dưới đây sai ở đâu mà no k chay.bạn nào phat hiện được thì giải thick cho m nhe.gửi vao (thaitinmo@gmail.com) cho m nhé.thank nhiều.minh chi mới học tới mảng thôi bạn nao giải thick thi đừng có đi wa đấy nha

    #inclucde
    #include
    #include
    void main()
    {
    clrscr();
    int a[100],i,j,n,dem=1;
    do
    {
    printf(“nhap so luong phan tu”);
    scanf(“%d”,&n);
    }while (n>100 )|| n<=0);
    for (i=1;i<=n;i++)
    {printf("nhap phan tu thu %d ",i);
    scanf("%d",&a[i]);
    }
    for(i=1;i<=n;i++)
    for (j=2;j<= int sqrt(a[i]);j++)
    { if a[i]% j !=0 dem++
    if int sqrt(a[i]) = dem printf("%d",a[i])
    }
    getch();
    }

    Reply
  • ngoan October 7, 2011, 11:06 pm

    mọi người có thể dùng hàm viết được hông vậy! ai viết được thì up lên đi

    Reply
  • FU October 31, 2011, 9:54 am

    đây là code để nhập hai số a,b và tìm các số nguyên tố trong khoảng :)

    /*
    Workshop 4
    Class ID : se0614
    Student ID : se02340
    Student Name : On Ngoc Khanh
    Due Date : 27/10/2011
    */

    #include
    #include
    #include

    int prime(int n)
    {
    int i,a;
    a=1;
    for (i=2;i<=n-1;i++)
    {
    if (n%i==0)
    {
    a=0;
    break;
    }
    }
    return a;
    }

    int main()
    {
    int kq,a,b,i;

    printf("Nhap a,b: ");
    scanf("%d",&a);
    scanf("%d",&b);

    for (i=a;i<=b;i++)
    {
    if (i==0) continue;
    if (i==1) continue;
    kq = prime(i);
    if (kq!=0) printf("%d ",i);
    }
    getch();
    }

    Reply

Leave a Comment