std ont log true 数组 blog roman func family
本实验采用了三种方法求素数,分别为:常规法、同余法以及筛选法,代码如下。
常规法:
- void func1(int max) { //方法1:从2到根号n
- bool m = true;
- for (int i = 2; i <= max; i++) {
- for (int j = 2; j <= sqrt(i); j++) {
- if (i % j == 0) {
- m = false;
- break;
- } else {
- continue;
- }
- }
- if (m) {
- std: :cout << i;
- }
- m = true;
- }
- }
同余法:
- void func2(int max) {//方法2:同余
- int PN[6] = { 2, 3, 5, 7, 11, 13 };//用以做素数判定
- for (int i = 2; i <= max; i++) {
- bool m = true;
- for (int j = 0; j < 6; j++) {
- if (i == PN[j]) {
- continue;
- }
- else if ((montgomary(i, PN[j] - 1) % PN[j]) == 1) {//蒙哥马利方法求高次幂
- continue;
- }
- else {
- m = false;
- break;
- }
- }
- if (m)
- std::cout << i;
- }
- }
筛选法:
- void func3(int max) { //筛选法,采用数组完成
- std: :vector < bool > PN(max, true);
- if (max > 1) {
- PN[0] = false;
- } else {
- return;
- }
- for (int i = 2; i < max; i++) {
- for (int j = 2; j <= sqrt(i); j++) {
- if (i % j == 0) {
- for (int k = i - 1; k <= max; k += i) {
- PN[k] = false;
- }
- break;
- }
- }
- }
- for (int i = 0; i < max; i++) {
- if (PN[i]) std: :cout << i + 1;
- }
- }
整体代码如下:
- #include < iostream > #include < string > #include < math.h > #include < vector >
- void func1(int max) { //方法1:从2到根号n
- bool m = true;
- for (int i = 2; i <= max; i++) {
- for (int j = 2; j <= sqrt(i); j++) {
- if (i % j == 0) {
- m = false;
- break;
- } else {
- continue;
- }
- }
- if (m) {
- std: :cout << i;
- }
- m = true;
- }
- }
- int montgomary(int N, int P) { //蒙哥马利算法,用以缩减乘法运算
- int odd = 1;
- while (P > 1) {
- if (P & 1) { //判断奇偶
- odd = N;
- P -= 1;
- }
- N *= N;
- P /= 2;
- }
- return N * odd;
- }
- void func2(int max) { //方法2:同余
- int PN[6] = {
- 2,
- 3,
- 5,
- 7,
- 11,
- 13
- }; //用以做素数判定
- for (int i = 2; i <= max; i++) {
- bool m = true;
- for (int j = 0; j < 6; j++) {
- if (i == PN[j]) {
- continue;
- } else
- if ((montgomary(i, PN[j] - 1) % PN[j]) == 1) { //蒙哥马利方法求高次幂
- continue;
- } else {
- m = false;
- break;
- }
- }
- if (m) std: :cout << i;
- }
- }
- void func3(int max) { //筛选法,采用数组完成
- std: :vector < bool > PN(max, true);
- if (max > 1) {
- PN[0] = false;
- } else {
- return;
- }
- for (int i = 2; i < max; i++) {
- for (int j = 2; j <= sqrt(i); j++) {
- if (i % j == 0) {
- for (int k = i - 1; k <= max; k += i) {
- PN[k] = false;
- }
- break;
- }
- }
- }
- for (int i = 0; i < max; i++) {
- if (PN[i]) std: :cout << i + 1;
- }
- }
- int main() {
- int max;
- std: :cin >> max; //获得上限
- //方法1
- func1(max);
- //方法2
- func2(max);
- //方法3
- func3(max);
- }
在较小的数量级上进行运算时,方法2、3要比1好上很多,例如当输入为5时,方法1用时2.367ms,后两者均为小于1ms。
在更大一些的数量级上进行运算时,方法3体现出其算法的优越性,例如当输入为100时,方法1用时3ms,方法2用时2ms,方法3用时1ms。
综上,方法3优于方法2优于方法1。
三种素数求法
来源: http://www.bubuko.com/infodetail-2353208.html