打印从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 。