In số nguyên tố mỗi hàng 10 số

[angelstar]

Chào các ban !
Mình có bài xin nhờ mấy bạn giúp mình giải nhé , sắp thi rùi.
Đề là:
Viết chương trình in ra các số nguyên tố từ 2 đến 1015 ,mỗi hàng mười số
Giúp mình nha , cảm ơn các bạn nhiều.

[iamvtn]

Đây là hàm kt số nguyên tố

bool LaNguyenTo(int n)
{
		bool co=true;
      if(n<2)
      {cout<<"Du lieu nhap sai va so do ";
   	return !co;}
   	else
      {
   		for(int i=2;i<=sqrt(n)+1;i++)
   		{
   			if(n%i==0)
      		        {
    				co=false;
      			        break;
      		         }
   		}
   	}
   return co;
}

Trong hàm main cậu cho vòng lặp for từ 2 đến 1015 rồi kt xem số nào thảo mãn thì in ra thôi.

[soda_chanhmuoi]

làm 1 hàm kiểm tra số nguyên tố (trả về kiểu bool hay int đều dc)
cho 1 biến i=0 , j=0
i chạy từ 2 -> 1015 dùng hàm kiểm tra số nguyên tố nếu là true (1) thì lưu số vào mảng a[j] rồi tăng j (j++).
xuất mảng a[] ra với điều kiện gặp j%10==0 thì xuống hàng.
vì sắp thi nên tự làm là tốt nhất!

[tienlbhoc]

Dùng phương pháp sàng era gì đó(tôi lâu không làm quên mất tên rồi, các bạn trong ngành thì tự biết) có phải nhanh không

[soda_chanhmuoi]

cái mà iamvtn viết hình như là phương pháp sàng thì phải?

[nicolasman]

ko biết thì đừng nói
ko phải sàng era gì đó đâu

[nicolasman]

nó co thể viết như sau

#define LEN 10000
int a[LEN] = {"0"}; //khoi tao la 0
for(int i = 2;i < LEN;i ++)
    if(a[i] == 0)
    {
      int k = 1;
      while(k*i < LEN)
            NT[i*k++] = 1;
       printf("%3d",i);
     }

ngoài ra bạn có thể dùng 2 vòng lặp for

[nguyen190887]

Avatar củasoda_chanhmuoi
soda_chanhmuoi soda_chanhmuoi là offline
Thành viên nhiệt tình

Gia nhập ngày: 04 2007
Bài viết: 160
Mặc định
làm 1 hàm kiểm tra số nguyên tố (trả về kiểu bool hay int đều dc)
cho 1 biến i=0 , j=0
i chạy từ 2 -> 1015 dùng hàm kiểm tra số nguyên tố nếu là true (1) thì lưu số vào mảng a[j] rồi tăng j (j++).
xuất mảng a[] ra với điều kiện gặp j%10==0 thì xuống hàng.
vì sắp thi nên tự làm là tốt nhất!

Đề bài chỉ bảo in ra thôi. Dùng mảng chi vậy bạn ???

[soda_chanhmuoi]

làm gì mà xuất 1 đống thông tin của mình thế? phòng trường hợp có nhu cầu dùng thêm, cũng là dễ dàng hơn, dễ hiểu hơn khi xuống hàng

[huynguyen]

Đề bài chỉ bảo in ra thôi. Dùng mảng chi vậy bạn ???

Dùng mảng để chạy sàng Eratosthene chứ chi ^,^
Ko thì với mỗi con số mình đều phải chạy hàm kt nguyên tố, rất bất tiện.
Đây là chương trình dùng hàm Erratosthene để giải bài toán này, cái chuyện xuất ra 10 số mỗi dòng thì mình có thể dùng mẹo nhỏ là lợi dụng việc 1 dòng có 80 ký tự nên mỗi biến xuất ra sẽ xuất với độ rộng là 8 (hơi tà đạo tý nhưng làm vậy nhanh hơn là dùng thêm 1 vòng for, hehe)

#include <iostream>
#include <iomanip>
#include <cmath>
#define maxn 1500
using namespace std;
void eratosthene(bool a[],int n)
{
    a[0] = false; a[1] = false;
    int i,j;
    for (i = 2; i <= n; i++) a[i] = true;
    for (i = 2; i <= int(sqrt(n)); i++)
        if (a[i]) for (j = 2; j <= n/i; j++) a[i*j] = false;
}
int main()
{
    bool sang[maxn];
    int n = 1015;
    eratosthene(sang,n);
    for (int i = 1; i <= 1015; i++)
         if (sang[i]) cout <<setw(8) <<i;
    system("pause");
    return 0;
}