C语言 找出所有小于 200 万的素数之和。欧拉项目，C
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18157322/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Find the sum of all the primes below two million. Project euler, C
提问by Lea
So, everything seems to be working nicely, but the program doesn't give me the correct answer. Mine is 142,915,960,832, whereas it should be 142,913,828,922. The differece is 2,131,910 (if I still can subtract numbers on paper haha) and I have no idea where did I get those two millions. Could anyone help me?
所以，一切似乎都运行良好，但程序没有给我正确的答案。我的是 142,915,960,832，而它应该是 142,913,828,922。差异是 2,131,910（如果我还能减去纸上的数字，哈哈），我不知道我从哪里得到那两百万。有人可以帮助我吗？
#include <stdio.h>
#include <math.h>
#define BELOW 2000000
int isaprime (int num);
int main (void) {
int i;
float sum = 0;
for (i = 2; i < BELOW; i++) {
if (isaprime(i) == 1) {
sum = sum + i;
printf ("\n%d\t%.1f", i, sum);
}
}
getch();
return 0;
}
int isaprime (int num) {
int i;
for (i = 2; i <= sqrt(num); i++) {
if (num % i == 0) {
return 0;
}
else {
;
}
}
return 1;
}
回答by jason
Using floatas the sumis the problem. The largest integer ksuch that all integers from [-k, k]are exactlyrepresentable in 32-bit float is 2^241; after that you will start losing precision in some integers. Since your sum is outside that range that, by an absurd margin, you lose precision and all bets are off.
使用floatassum是问题所在。k使得所有整数[-k, k]都可以用 32 位浮点数精确表示的最大整数是 2^24 1；之后，您将开始失去某些整数的精度。由于您的总和超出了该范围，以荒谬的幅度，您会失去精确度，所有赌注都将取消。
You need to change to a larger type like long(assuming it's 64-bits on your machine). Make the change, and you'll get right answer (as I did with you code):
您需要更改为更大的类型long（假设您的机器上是 64 位）。进行更改，您将得到正确答案（就像我对您的代码所做的那样）：
[ec2-user@ip-10-196-190-10 ~]$ cat -n euler.c
1 #include <stdio.h>
2 #include <math.h>
3
4 #define BELOW 2000000
5
6 int isaprime (int num);
7
8 int main (void) {
9
10 int i;
11 long sum = 0;
12
13 for (i = 2; i < BELOW; i++) {
14
15 if (isaprime(i) == 1) {
16 sum = sum + i;
17 }
18 }
19 printf("sum: %ld\n", sum);
20
21 return 0;
22 }
23
24 int isaprime (int num) {
25
26 int i;
27
28 for (i = 2; i <= sqrt(num); i++) {
29 if (num % i == 0) {
30 return 0;
31 }
32 else {
33 ;
34 }
35 }
36
37 return 1;
38 }
[ec2-user@ip-10-196-190-10 ~]$ gcc euler.c -lm
[ec2-user@ip-10-196-190-10 ~]$ ./a.out
sum: 142913828922
1: 23 explicit bits in the mantissa plus one hidden bit.
1: 尾数中的 23 个显式位加上 1 个隐藏位。
回答by user448810
As @LeeDanielCrocker suggested, here is an implementation of the Sieve of Eratosthenesthat solves the problem instantaneously:
正如@LeeDanielCrocker 所建议的，这里是Eratosthenes 筛法的一个实现，它可以立即解决问题：
#include <stdio.h>
#include <string.h>
#define ISBITSET(x, i) (( x[i>>3] & (1<<(i&7)) ) != 0)
#define SETBIT(x, i) x[i>>3] |= (1<<(i&7));
#define CLEARBIT(x, i) x[i>>3] &= (1<<(i&7)) ^ 0xFF;
long long sumPrimes(int n) {
char b[n/8+1];
long long i, p;
long long s = 0;
memset(b, 255, sizeof(b));
for (p=2; p<n; p++) {
if (ISBITSET(b,p)) {
//printf("%d\n", p);
s += p;
for (i=p*p; i<n; i+=p) {
CLEARBIT(b, i); }}}
return s; }
int main(void) {
printf("%lld\n", sumPrimes(2000000));
return 0; }
At ideone, that returns in thirty milliseconds. The optimized version shown below, which sieves only on odd numbers and handles 2 separately, runs in zero time (less than ten milliseconds) at ideone.
在ideone，它会在 30 毫秒内返回。下面显示的优化版本，仅对奇数进行筛选并单独处理 2，在ideone 上以零时间（小于 10 毫秒）运行。
#include <stdio.h>
#include <string.h>
#define ISBITSET(x, i) (( x[i>>3] & (1<<(i&7)) ) != 0)
#define SETBIT(x, i) x[i>>3] |= (1<<(i&7));
#define CLEARBIT(x, i) x[i>>3] &= (1<<(i&7)) ^ 0xFF;
long long sumPrimes(int n) {
int m = (n-1) / 2;
char b[m/8+1];
int i = 0;
int p = 3;
long long s = 2;
int j;
memset(b, 255, sizeof(b));
while (p*p < n) {
if (ISBITSET(b,i)) {
s += p;
j = (p*p - 3) / 2;
while (j < m) {
CLEARBIT(b, j);
j += p; } }
i += 1; p += 2; }
while (i < m) {
if (ISBITSET(b,i)) {
s += p; }
i += 1; p += 2; }
return s; }
int main(void) {
printf("%lld\n", sumPrimes(2000000));
return 0; }
If you're interested in programming with prime numbers, I modestly recommend this essayat my blog; it describes both algorithms given above, covers all the algorithms you will need to solve the prime-number problems at Project Euler, and includes source code in C and four other languages.
如果你对用质数编程感兴趣，我在我的博客上谦虚地推荐这篇文章；它描述了上面给出的两种算法，涵盖了解决 Project Euler 中的素数问题所需的所有算法，并包括 C 和其他四种语言的源代码。
回答by H.T
Please try this way, fast and simple:
请尝试这种方式，快速而简单：
int const MAX = 2000000;
int checkPrime(int n){
int range = n;
for (int i = 2; i < range; i++){
if (n%i == 0){
return 0;
}
range = n / i;
}
return 1;
}
int solution(){
double sum = 0;
for (int i = 2; i < MAX; i++){
if (checkPrime(i) == 1){
sum += i;
}
}
return sum;
}
回答by Praveen M P
Although this answer is not pitch-perfect, it would take less than 3 secondsto execute. Code in C#.
Step 1- omitted numbers which are divisible by 2,3, 5,7
Step 2 - To check prime number we don't need to divide given number with all the numbers. using square root will reduce the code to half time.
虽然这个答案并不完美，但执行时间不到3 秒。C# 中的代码。
第 1 步 - 省略可被 2,3, 5,7 整除的数字
第 2 步 - 要检查素数，我们不需要将给定数字与所有数字相除。使用平方根会将代码减少一半。
using System;
namespace ProjectEuler
{
class Program
{
static void Main(string[] args)
{
long i, j, sum = 17;
bool flag = true;
for (i = 2; i < 2000000; i++)
{
if ((i % 2) != 0 && (i % 3) != 0 && (i % 5) != 0 && (i % 7) != 0)
{
flag = true;
for (j = 2; j <= Math.Sqrt(i); j++)
{
if (i % j == 0)
{
flag = false;
}
}
if (flag == true)
{
sum = sum + i;
}
}
}
Console.WriteLine(sum);
Console.ReadLine();
}
}
}
回答by Netikar Sundeep
Addition of prime No upto 2 million below is the code.
Please let me know if anyone have doubt.
<html>
<body>
<input id="inp" width="200px"/>
<input type="button" onClick="onPress()" value="Check"/>
</body>
<script>
function onPress()
{
var value= document.getElementById("inp").value;
var arr=[2,3,5,7], add=17;
for(var divisor=2; divisor<value; divisor++)
{
var prime= true
if(divisor%2==0 || divisor%3==0 || divisor%5==0 || divisor%7==0)
{
prime=false;
}
if(prime !=false)
{
for(var j=0; j<arr.length; j++)
{
if(divisor%arr[j]==0)
{
prime=false;
}
}
}
if(prime==true)
{
arr.push(divisor);
add+= divisor;
}
}
console.log(add);
}
</script>
</html>
回答by Yup.
Here's my javascript solution:
这是我的 javascript 解决方案：
function sumPrimes(num) {
// determine if a number is prime
function isPrime(n) {
if (n === 2) return true;
if (n === 3) return true;
if (n % 2 === 0) return false;
if (n % 3 === 0) return false;
var i = 5;
var w = 2;
while (i * i <= n) {
if (n % i === 0) {
return false;
}
i += w;
w = 6 - w;
}
return true;
}
// subtract 1 for 'not being prime' in my context
var sum = isPrime(num) ? num - 1 : -1;
for (var x = 0; x < num; x++) {
if (isPrime(x) === true) {
sum += x;
}
}
return sum;
}
回答by Debjeet Sarkar
#include<stdio.h>
#define MAX 2000001
long long a[MAX],c=0;
main()
{
long long i=0,k,j,p,temp=0;
long long inc=0;
for(i=0;i<MAX;i++)
a[i]=i;
for(j=2;j*j<MAX;j++)
{
temp=j;
inc=2*temp;
k=((MAX-1)/temp)-1;
while(k)
{
printf("%d",inc);
printf("\n");
if(a[inc]!=0)
a[inc]=0;
inc+=temp;
--k;
}
}
for(p=0;p<MAX;p++)
{
if(a[p]!=0)
c=c+a[p];
printf("%lld",a[p]);
printf("\n");
}
printf(" The sum is : %lld",c-1);
}
回答by Rahul Tripathi
You can use the Sieve algorithmas this would be the fastest of all:-
您可以使用Sieve 算法，因为这将是最快的：-
In C++
在 C++ 中
std::vector<int> generate_primes( int n )
{
std::vector<bool>sieve( n, true ) ;
for( std::size_t i = 2 ; i < sieve.size() ; ++i ) if( sieve[i] )
for( auto j = i*i ; j < sieve.size() ; j += i ) sieve[j] = false ;
std::vector<int> primes ;
for( std::size_t i = 2 ; i < sieve.size() ; ++i )
if( sieve[i] ) primes.push_back(i) ;
return primes ;
}
回答by Farzi Coders
You can check the following code in c:
您可以在 c 中检查以下代码：
/*Program to print sum of all prime numbers upto 2000000*/
/*To check whether a number is prime or not it takes n^2 time by
brute force but this program is sqrt(n) according to
mathematical rules to check prime number efficiently.
*/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAX 2000000
int main()
{
int i,j;
unsigned long int prod=0;
int prime;
for(i=2;i<=MAX;i++){
prime=1;
for(j=2;j<(int)(sqrt(i)+1);j++){
if(i%j==0){
prime=0;
break;
}
}
if(prime==1){
prod=prod+i;
}
}
printf("%ld",prod);
return 0;
}
