使用筛选法的C++程序求1000以内的素数 |holyya.com

使用筛选法的C++程序求1000以内的素数

2023-07-03 14:58:45 深夜i -- --

筛选法 C++程序 1000以内素数

求素数是计算机科学中一个经典的问题，并且它有多种解决方法。其中一种常用的方法是使用筛选法。在这篇文章中，我们将介绍如何使用筛选法的C++程序求1000以内的素数。

什么是素数？

首先，让我们来看看什么是素数。素数是指在大于1的自然数中，只能被1和自身整除的数。例如，2、3、5、7等都是素数，而4、6、8等不是素数。

使用筛选法求素数

筛选法是一种基本的求素数方法。这个方法的基本思路是，从2开始，将每个素数的倍数都标记成非素数。例如，从2开始，将2的倍数都标记成非素数，然后从3开始，将3的倍数都标记成非素数，直到所有的数字都被标记过。

下面是使用筛选法求1000以内素数的C++程序：


#include <iostream>
#include <cmath>
using namespace std;
int main() {
 const int N = 1000;
 bool nums[N+1] = { false };
 
 for(int i=2; i<=sqrt(N); i++) {
  if(!nums[i]) {
   for(int j=i*i; j<=N; j+=i) {
    nums[j] = true;
   }
  }
 }
 for(int i=2; i<=N; i++) {
  if(!nums[i])
    cout<<i<<endl;
  
 }
 return 0;
}

程序分析

上面的程序首先定义了一个常量N，表示要求的素数范围是1000以内。然后创建一个bool类型的数组nums，表示每个数字是否是素数。数组中的每个元素初始化为false。

接下来的for循环从2开始，循环到sqrt(N)（sqrt函数表示取N的平方根）。如果当前数字i是素数（即nums[i]为false），则将i的倍数都标记成非素数。这样，经过这一步操作后，数组中剩下的元素就是1000以内的素数了。

最后一个for循环遍历数组nums，输出其中不为素数的元素。通过这个程序，我们可以得到1000以内的素数，它们是：

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997

可以看到，1000以内的素数有168个。这个方法可以扩展到更大的素数范围，并且速度很快。所以，在求素数问题上，筛选法是一个非常有效的解决方法。

上一篇: idea打包java可执行jar包

下一篇: C++如何判断两个浮点数相等

评论区

()

相似文章