các bác cho mình hỏi bài tập về số nguyên tố với

[anhtuantvb09]

mình muốn viết một chương trình tìm các số nguyên tố nhỏ hơn n(với n nhập vào từ bàn phím).mong các bác chỉ cho mình với.mình cảm ơn

[vnhack]

Tôi nghĩ thế nào trong cái diễn đàn này có nhiểu câu hỏi giống như bạn, tập Search đi

[legenday]

Thuật toán tìm số nguyên tố:

Số nguyên tố là số chia hết cho 1 và chính nó.
Thế nên ta chỉ cần tạo một vòng lặp kiểm tra xem số đó có chia hết từ 1 đến căn bậc hai của số đó.Nếu chia hết thì trả ra kết quả không phải là số nguyên tố ,còn trái lại sau cả vòng lặp đó mà không chia hết cho số nào thì trả ra là số nguyên tố .

còn việc đếm số nguyên tố thì tạo thêm một vòng lặp bên ngoài nữa chạy từ 1 đến n và từng bước lặp thử xem nó có là số nguyên tố không ?( thêm một biến để đếm mỗi lần thấy số nguyên tố )

( Như vậy là phải sử dụng tới 2 vòng lặp và một vài biến phụ khác)

hoặc bạn có thể viết 2 hàm ,một hàm kiểm tra số nguyên tố , và hàm còn lại sử dụng hàm kiểm tra số nguyên tố để đếm xem từ 1 đến n là được bao nhiêu số.

[nguyenthanhhungcntt]

mình muốn viết một chương trình tìm các số nguyên tố nhỏ hơn n(với n nhập vào từ bàn phím).mong các bác chỉ cho mình với.mình cảm ơn

Code đây:chúc bạn thành công
// Prime.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<stdio.h>
#include<conio.h>
#define N 1000
int IsPrime(int n){

int i,Prime=1;
for(i=2;i<n/2;i++)
if(n%i==0)
Prime=0;
return Prime;
}


void ListPrime(int n){
int i;
for(i=2;i<=n;i++)
if(IsPrime(i))
printf(" %d",i);

}
void main()
{
int n;
printf("N=");
scanf("%d",&n);
ListPrime(n);
getch();
}

[ilit]

int IsPrime(int n)
{
	int i,Prime=1;
	for(i=2;i<n/2;i++)
		if(n%i==0) Prime=0;
	return Prime;
}

Ta chỉ cần cho i chạy từ 2 đến căn bậc 2 của n là được, vì sqrt(n)*sqrt(n)+1 > n nên n sẽ không chia hết cho các số từ sqrt(n)+1. Và hàm IsPrime cũng không cần phải đặt thêm biến Prime, chỉ cần n chia hết cho i thì return 0, còn không thì return 1.

int IsPrime(int n)
{
	for(int i=2; i<=sqrt(n); i++)
		if(n%i==0) return 0;
	return 1;
}

Chú ý: Phải include thư viện math.h trước khi dùng hàm sqrt.