首页 > 代码库 > 欧拉计划（1~3）ps：以后看题一定要认真
欧拉计划（1~3）ps：以后看题一定要认真
那天的题挺简单的
下面来看下
No1
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
//project euler num1#include <stdio.h>#include <stdlib.h>#include <string.h>int main(){ int sum = 0; int i; for(i = 0; i < 1000; i++) { if(i % 3 == 0 || i % 5 == 0) sum += i; } printf("The sum is %d\n", sum);}第一题很简单，不解释~
No 2
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms
第二题是求斐波那契数列小于 4e6 的那些偶数项的和，很简单的想到了递归算法
//project euler pro02#include <iostream>#include <string>#include <vector>using namespace std;int fib_temp[10000];//避免重复运算，算好的项存入数组int fib(int n){ if(n == 1) { fib_temp[0] = 1; return fib_temp[0]; } else if( n == 0) { fib_temp[1] = 2; return fib_temp[1]; } else { if(fib_temp[n - 1] != 0) { if(fib_temp[n - 2] != 0) return fib_temp[n - 1] + fib_temp[n - 2];//如果已经预存，直接返回 else fib_temp[n - 2] = fib( n - 2); return fib_temp[n - 1] + fib_temp[n - 2]; } else { fib_temp[n - 1] = fib(n - 1); fib_temp[n - 2] = fib(n - 2); return fib_temp[n - 1] + fib_temp[n - 2]; } }}int sum_even_fib(int top_num){ int i = 0; int sum = 0; int temp = 0; while(1) { if(i % 2 == 0) { if((temp = fib(i)) < top_num) sum += temp; else break; } i++; } return sum;}int main(){ int sum = sum_even_fib(400000000); cout << sum << endl; return 0;} 就是这样，没有选用最基本的递归方法是因为效率过低，不如把算好的想先存入数组，避免重复计算。
但是这让我想起了之前的动态规划算法：
递归算法是很简单的自顶向下，从上可以看出是从n一步步的计算到第一项；
但是动态规划恰恰相反，它是先从第一项开始计算，然后把算好的结果存入数组以备后用。
1 //project euler pro02 2 #include <iostream> 3 #include <string> 4 #include <vector> 5 using namespace std; 6 7 int fib_temp[10000]; 8 //設立預存數組 9 int fib(int n) 10 { 11 if( n == 0 || n == 1) 12 { 13 if(fib_temp[0] == 0) 14 fib_temp[0] = 1; 15 if(fib_temp[1] == 0) 16 fib_temp[1] = 2; 17 //對前兩項初始化 18 } 19 else 20 { 21 for(int i = 2; i <= n; i++) 22 { 23 if(fib_temp[i] == 0) 24 fib_temp[i] = fib_temp[i - 1] + fib_temp[i - 2]; 25 //用循環計算後面的項 26 } 27 } 28 return fib_temp[n]; 29 //直接返回數組中的項 30 } 31 32 int sum_even_fib(int top_num) 33 { 34 int i = 0; 35 int sum = 0; 36 int temp = 0; 37 while(1) 38 { 39 if((temp = fib(i)) % 2 == 0) 40 { 41 if(temp < top_num) 42 sum += temp; 43 else 44 break; 45 } 46 cout << fib(i) << endl; 47 i++; 48 } 49 return sum; 50 } 51 int main() 52 { 53 int sum = sum_even_fib(4e6); 54 cout << sum << endl; 55 return 0; 56 } No3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
我会说就是这个我没有看清楚题么，我看做是求小于这个数的所有素数~
但是题目是求小于这个数的最大素因子。
悲伤~~
好吧，两个都做完了，先看计算最大素因子。
#include <iostream> 2 #include <string> 3 #include <vector> 4 #include <math.h> 5 6 using namespace std; 7 8 9 bool is_prime(long long int i) 10 { 11 long long int j; 12 for(j = 2; j <= sqrt(i); j ++) 13 { 14 if(i % j == 0) 15 return false; 16 } 17 if(j > sqrt(i)) 18 return true; 19 } 20 //这是判断素数的 21 22 void max_prime_facter(long long int n) 23 { 24 if(is_prime(n)) 25 { 26 cout << n << endl; 27 return; 28 //如果n本身就是素数，直接输出 29 } 30 for(long long int i = 2; i < (n / 2); ++i) 31 { 32 if(n % i == 0) 33 { 34 n = n / i; 35 //如果找到一个小的因子，替换n为n/i 36 cout << "factor is " << i << endl; 37 i = 2; 38 //重置循环变量 39 if(is_prime(n)) 40 { 41 cout << n << endl; 42 //如果在过程中发现n变为了素数，说明 得到了最大的素因子 43 break; 44 } 45 } 46 } 47 } 48 49 int main(int argc, const char *argv[]) 50 { 51 long long int n = 600851475143; 52 max_prime_facter(n); 53 return 0; 54 } 看~不难吧。
那么问题就来了， 挖掘机到底那家强！！
小扯一下，那么如果我想输出小于这个数的所有素数呢？
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <stdio.h> 5 #include <stdlib.h> 6 #include <string.h> 7 #include <math.h> 8 using namespace std; 9 10 bool is_prime(long long int i) 11 { 12 for(long long int j = 2; j <= sqrt(i); j ++) 13 { 14 if(i % j == 0) 15 return false; 16 } 17 if(i > sqrt(i)) 18 return true; 19 } 20 //判断素数的函数 21 vector<int> vec_prime; 22 //一个存放素数的数组 23 void prime_number(long long int n) 24 { 25 long long int max; 26 for (int i = 2; i < n; i++) 27 { 28 if(vec_prime.size() != 0) 29 //一开始数组内是没有元素的 30 { 31 vector<int>::iterator it ; 32 for( it = vec_prime.begin(); it != vec_ prime.end(); ++it) 33 { 34 if(i % (*it) == 0) 35 break; 36 //依次判断数组内有没有其的因子 37 } 38 if(it != vec_prime.end()) 39 continue; 40 //这表示有他的素因子 41 } 42 if(is_prime(i) == true) 43 //到这里说明数组中没有这个数的因子 44 //因为我们知道一切正整数都可以表示成素数的乘积 45 //反之，如果这个数不能表示成素数的乘积 46 //那么这个数本身很可能就是素数 47 //所以判断他是否是素数，是的话就加入数组 48 { 49 vec_prime.push_back(i); 50 cout << i << endl; 51 //依次输出素数 52 } 53 } 54 return ; 55 } 56 57 int main() 58 { 59 60 long long int n = 600851475143; 61 prime_number(n); 62 return 0; 63 } 可以看到这个算法其实是非常快速的~
最后再说一下：
今天学习了c++中的两个新的数据类型long long int 和 _int64.
参考文章:
http://www.cnblogs.com/jiai/articles/2613900.html
http://www.cnblogs.com/felove2013/articles/3880590.html
欧拉计划（1~3）ps：以后看题一定要认真