實(shí)驗(yàn)1.1 求素?cái)?shù)表

輸出小于等于n(n >= 2正整數(shù))的素?cái)?shù)。要求每行輸出10個(gè)素?cái)?shù)，盡可能采用較優(yōu)的算法。

求素?cái)?shù)表，已經(jīng)有了成熟的解法。最簡單的就是對每個(gè)數(shù)m從2到(m-1)進(jìn)行檢查，O(n²)。稍微提高一點(diǎn)的就是對每個(gè)數(shù)m從2到int(sqrt(n))進(jìn)行檢查，同時(shí)不對偶數(shù)進(jìn)行檢查，為O(n * sqrt(n) / 2)，也就是下面的解法。

#include <cstdio> #include <cmath> const int maxn = 1000; int prime[maxn] = {2}, len = 1;void judgePrime(int n) {for (int i = 3; i <= n; i += 2) {int sqr = sqrt(i), flag = 1;for (int j = 2; j <= sqr; ++j) {if (i % j == 0) {flag = 0;break;}}if (flag) prime[len++] = i;} }int main(int argc, char** argv) {judgePrime(500);printf("%4d ", prime[0]);for (int i = 1; i < len; ++i) {printf(" %4d", prime[i]);if ((i + 1) % 10 == 0) printf("\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【数据结构教程 李春葆】上机实验--第一章实验题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。