打印从1到100的素数
此c ++代码打印出以下素数： 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97。
但我认为这不是我的书想要写的方式。 它提到了一些关于数字的平方根的东西。 所以我确实尝试将我的第二个循环改为for (int j=2; j<sqrt(i); j++)但它没有给我我需要的结果。
我如何才能将此代码更改为我的书所希望的方式？
int main () { for (int i=2; i<100; i++) for (int j=2; j<i; j++) { if (i % j == 0) break; else if (i == j+1) cout << i << " "; } return 0; }
素数是具有两个不同除数的整数，即1和数字本身。 编写，运行和测试C ++程序，查找并打印小于100的所有素数。（提示：1是素数。对于每个从2到100的数字，找到Remainder = Number％n，其中n的范围是2 to sqrt（number）。\如果n大于sqrt（数字），则该数字不能被n整除。为什么？如果任何剩余等于0，则该数字不是素数。）
三种方式：
1。
int main () { for (int i=2; i<100; i++) for (int j=2; j*j<=i; j++) { if (i % j == 0) break; else if (j+1 > sqrt(i)) { cout << i << " "; } } return 0; }
2。
int main () { for (int i=2; i<100; i++) { bool prime=true; for (int j=2; j*j<=i; j++) { if (i % j == 0) { prime=false; break; } } if(prime) cout << i << " "; } return 0; }
3。
#include int main() { std::vector primes; primes.push_back(2); for(int i=3; i < 100; i++) { bool prime=true; for(int j=0;j
编辑：在第三个例子中，我们跟踪所有先前计算的素数。 如果一个数字可以被一个非素数除尽，那么还有一些素数<=该除数它也可以被除数。 这减少了计算的primes_in_range / total_range因子。
如果j 等于 sqrt(i)它也可能是一个有效因子，不仅如果它更小 。
要在内循环中迭代并包含sqrt(i) ，您可以编写：
for (int j=2; j*j<=i; j++)
（与使用sqrt(i)相比，这有利于不需要转换为浮点数。）
如果数字有除数，则其中至少有一个必须小于或等于数字的平方根。 当你检查除数时，你只需要检查平方根，而不是一直到被测试的数字。
这是我非常简单的c ++程序，用于列出2到100之间的素数。
for(int j=2;j<=100;++j) { int i=2; for(;i<=j-1;i++) { if(j%i == 0) break; } if(i==j && i != 2) cout<
实际上更好的解决方案是使用“一个筛子或素数筛子”，“这是一种快速的寻找素数的算法”..维基百科
简单（但不是更快）的算法称为“eratosthenes筛”，可以在以下步骤中完成（再次来自维基百科）：
- 创建从2到n的连续整数列表：（2,3,4，…，n）。
- 最初，让p等于2，即第一个素数。
- 从p开始，以p为增量进行计数，并在列表中将每个数字标记为大于p本身。 这些数字将是2p，3p，4p等; 请注意，其中一些可能已被标记。
- 在列表中找到未标记的第一个大于p的数字。 如果没有这样的号码，请停止。 否则，让p现在等于这个数字（这是下一个素数），并从步骤3开始重复。
使用Sieve of Eratosthenes逻辑，我能够以更快的速度实现相同的结果。
我的代码演示 VS 接受了答案 。
比较count ，我的代码需要很少的迭代才能完成工作。 最后检查不同N值的结果。
为什么这段代码比已经接受的代码表现更好：
– 在整个过程中甚至不检查偶数。
– 内圈和外圈都只在可能的范围内进行检查。 没有多余的检查。
码：
int N = 1000; //Print primes number from 1 to N vector primes(N, true); for(int i = 3; i*i < N; i += 2){ //Jump of 2 for(int j = 3; j*i < N; j+=2){ //Again, jump of 2 primes[j*i] = false; } } if(N >= 2) cout << "2 "; for(int i = 3; i < N; i+=2){ //Again, jump of 2 if(primes[i] == true) cout << i << " "; }
对于N = 1000 ，我的代码需要1166次迭代，接受的答案需要5287次（慢4.5倍）
对于N = 10000 ，我的代码需要14637次迭代，接受的答案需要117526次（慢8次）
对于N = 100000 ，我的代码需要175491次迭代，接受的答案需要2745693（慢15.6次）
寻找高达100的素数是特别好和容易：
printf("2 3 "); // first two primes are 2 and 3 int m5 = 25, m7 = 49, i = 5, d = 4; for( ; i < 25; i += (d=6-d) ) { printf("%d ", i); // all 6-coprimes below 5*5 are prime } for( ; i < 49; i += (d=6-d) ) { if( i != m5) printf("%d ", i); if( m5 <= i ) m5 += 10; // no multiples of 5 below 7*7 allowed! } for( ; i < 100; i += (d=6-d) ) // from 49 to 100, { if( i != m5 && i != m7) printf("%d ", i); if( m5 <= i ) m5 += 10; // sieve by multiples of 5, if( m7 <= i ) m7 += 14; // and 7, too }
100的平方根是10 ，所以Eratosthenes的筛子与2-3轮的再现使用了3以上不超过10的素数的倍数 - 即。 仅5和7 ！ - 以增量方式筛选低于100的6- coprimes。
可以将for循环更改为for (int j=2; j<=sqrt(i); j++)但是您还需要更改其他内容。 特别注意您的打印条件，
else if (i == j+1) { cout << i << " "; }
如果你只迭代到sqrt(i) ，为什么永远不会被触发？ 在哪里可以移动cout来改变它？ （提示：您可能希望将打印移出循环，然后使用某种类型的标志变量）
我使用以下代码检查数字是否为素数（当然使用sqrt）：
bool IsPrime(const unsigned int x) { const unsigned int TOP = static_cast( std::sqrt( static_cast( x ) ) ) + 1; for ( int i=2; i != TOP; ++i ) { if (x % i == 0) return false; } return true; }
我使用这种方法来确定素数：
#include using std::cout; using std::cin; using std::endl; #include void initialize( unsigned int *, const unsigned int ); void show_list( const unsigned int *, const unsigned int ); void criba( unsigned int *, const unsigned int ); void setItem ( unsigned int *, const unsigned int, const unsigned int ); bool IsPrime(const unsigned int x) { const unsigned int TOP = static_cast( std::sqrt( static_cast( x ) ) ) + 1; for ( int i=2; i != TOP; ++i ) { if (x % i == 0) return false; } return true; } int main() { unsigned int *l; unsigned int n; cout << "Ingrese tope de criba" << endl; cin >> n; l = new unsigned int[n]; initialize( l, n ); cout << "Esta es la lista" << endl; show_list( l, n ); criba( l, n ); cout << "Estos son los primos" << endl; show_list( l, n ); } void initialize( unsigned int *l, const unsigned int n) { for( int i = 0; i < n - 1; i++ ) *( l + i ) = i + 2; } void show_list( const unsigned int *l, const unsigned int n) { for( int i = 0; i < n - 1; i++ ) { if( *( l + i ) != 0) cout << l[i] << " - "; } cout << endl; } void setItem( unsigned int *l, const unsigned int n, const unsigned int p) { unsigned int i = 2; while( p * i <= n) { *( l + (i * p - 2) ) = 0; i++; } } void criba( unsigned int *l, const unsigned int n) { for( int i = 0; i * i <= n ; i++ ) if( IsPrime ( *( l + i) ) ) setItem( l, n, *(l + i) ); }
使用可分性规则素数可以在O（n）中找到，它是真正有效的可分性规则
解决方案将基于数字的个别数字…
#include using namespace std; void main() { int num,i,j,prime; cout<<"Enter the upper limit :"; cin>>num; cout<<"Prime numbers till "<
这是我对Eratosthenes筛选的实现（适用于2和n之间的素数）
#include int main (){ int n=0; std::cout << "n = "; std::cin >> n; std::cout << std::endl; if (n==0 || n==1){ std::cout << "No primes in this range" << std::endl; return 0; } const int array_len = n-2+1; int the_int_array[array_len]; for (int counter=2; counter <=n; counter++) the_int_array[counter-2]=counter; int runner = 0; int new_runner = 0; while (runner < array_len ){ if (the_int_array[runner]!=0){ new_runner = runner; new_runner = new_runner + the_int_array[runner]; while (new_runner < array_len){ the_int_array[new_runner] = 0; new_runner = (new_runner + the_int_array[runner]); } } runner++; } runner = 0; while (runner < array_len ){ if (the_int_array[runner]!=0) std::cout << the_int_array[runner] << " "; runner++; } std::cout << std::endl; return 0;
}
#include "stdafx.h" #include using namespace std; void main() { int f =0; for(int i=2;i<=100;i++) { f=0; for(int j=2;j<=i/2;j++) { if(i%j==0) { f=1; break; } } if (f==0) cout<
这是我从一个简单的博客的方法：
//Prime Numbers generation in C++ //Using for loops and conditional structures #include using namespace std; int main() { int a = 2; //start from 2 long long int b = 1000; //ends at 1000 for (int i = a; i <= b; i++) { for (int j = 2; j <= i; j++) { if (!(i%j)&&(i!=j)) //Condition for not prime { break; } if (j==i) //condition for Prime Numbers { cout << i << endl; } } } }
- 请参阅： http ： //www.programmingtunes.com/generation-of-prime-numbers-c/#sthash.YoWHqYcm.dpuf
找不到。 是否是素数C ++：
#include #include using namespace std; int main(){ int n, counter=0; cout <<"Enter a number to check whether it is prime or not \n"; cin>>n; for(int i=2; i<=n-1;i++) { if (n%i==0) { cout<
我是基于ProdigySim第二种方法最流行的答案在perl中完成的。 我不得不在perl中添加一个等效的break ， last ，在print $i . " \n"; print $i . " \n"; 避免两次输出素数。
#!/bin/perl use strict; for(my $i=2; $i < 100; $i++){ my $prime = 1; for (my $j=2; $j*$j<=$i; $j++){ if ($i % $j == 0){ $prime = 0; last; } if($prime) { print $i . " \n"; last; } } }
一个打印“N”素数的简单程序。 您可以将N值用作100。
#include using namespace std; int main() { int N; cin >> N; for (int i = 2; N > 0; ++i) { bool isPrime = true ; for (int j = 2; j < i; ++j) { if (i % j == 0) { isPrime = false ; break ; } } if (isPrime) { --N; cout << i << "\n"; } } return 0; }
这是一个简单的代码，用于打印所有素数，直到给定数字n，
#include #include void main() { clrscr(); int n,i,j,k; cout<<"Enter n\n"; cin>>n; for(i=1;i<=n;i++) { k=0; for(j=1;j<=i;j++) { if((i%j)==0) k++; } if(k==2) cout<
我总是使用这个（它很容易和快速）：
#include using namespace std; int i,j; bool b[101]; int main( ) { for(i=2;i<101;i++){ b[i]=true; } for(i=1;i<101;i++){ if(b[i]){ cout<
以下是此代码的输出：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
这本书似乎是由加里布朗森编写的“工程师和科学家的C ++”（谷歌搜索）。
这是一个可能的答案吗？ 恕我直言，这是令人惊讶的。
我不得不读几遍问题（从书中）。 我的解释：
对于每个数字N：2 <= N <100，检查它是否为素数。
怎么样？ 对于每个除数D：2 <= D
试试看：
N = 2, sqrt(2) ≈ 1.41, D = 2, 2 < 1.41 ? no 2 > 1.41 ? yes 2 is prime. N = 3, sqrt(3) ≈ 1.73, D = 2, 2 < 1.73 ? no 2 > 1.73 ? yes 3 is prime. N = 4, sqrt(4) = 2.00, D = 2, 2 < 2.00 ? no 2 > 2.00 ? no 4 is not prime. N = 5, sqrt(5) ≈ 2.24, D = 2, 2 < 2.24 ? yes 5 % 2 > 0? yes D = 3, 3 < 2.24 ? no 3 > 2.24 ? yes 5 is prime. N = 6, sqrt(6) ≈ 2.45, D = 2, 2 < 2.45 ? yes 6 % 2 = 0 2 > 2.45 ? no 6 is not prime.
据我所知，这就是应该如何找到素数，
没有筛子（更快，更快），
但是： 答案就在于问题！ 奇怪？
速度？ 素数<400,000：不到10秒（在我的手表上，劳力士，我在市场上买了它，卖家说这是一个真正的，一个真正的两个法式长棍面包的价格，还有12个真正的钻石）。
让我们计算素数（我不会显示代码;）：664579 primes <10,000,000：5秒。
#include "stdafx.h" #include #include using namespace std; int main() { double rt; for (int d = 2, n = 2; n < 100; d = 2, n++) { for (rt = sqrt(n); d < rt; d++) if (n % d == 0) break; if (d > rt) cout << n << " "; } getchar(); // 25 primes :-) }
删除了早期的答案（如其他答案）和筛子。
希望我很快得到我的下一个“死灵法师”徽章。
我问作者：在你的书中：“C ++ for E＆S”是一个关于素数的练习，[xrcs] ... [/ xrcs]。 七年前有人问过：SO / q / 5200879
几天前，我给出了答复：SO / a / 49199435
您认为这是一个合理的解决方案，还是解决方案。
他回答说：彼得，我在练习时从来没有真正考虑过具体的解决方案，
所以我不能说我有你的确切解决方案。 C ++的乐趣在于，人们可以提出真正有创意的解决方案和优秀的代码，因为乍一看，它看起来就像你已经完成的那样。
谢谢你发送它！
布朗森博士
我去了https://youtu.be/1175axY2Vvw
PS。 筛子： https ： //pastebin.com/JMdTxbeJ
试试吧。 没有任何额外的内置function，它很容易。
#include int prime(int n,int r){ for(int i=2;n<=r;i++){ if(i==2 || i==3 || i==5 || i==7){ std::cout<
2,3,5,7的测试足够高达120 ，所以100可以。
有低于100的 25个素数，低于121的30 = 11 * 11 。