【ProjectEuler】ProjectEuler_050（找到100万以内最多连续素数的和，它也同时是个素数）

2024-03-06 12:58
文章标签 100 连续 找到 素数 以内 050 projecteuler

本文主要是介绍【ProjectEuler】ProjectEuler_050（找到100万以内最多连续素数的和，它也同时是个素数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！ 

#pragma once#include <windows.h>
#include <vector>
#include <set>using namespace std;class MoonMath
{
public:MoonMath(void);~MoonMath(void);//************************************// Method:    IsInt// Access:    public// Describe:  判断double值在epsilon的范围内是否很接近整数//            如1.00005在epsilon为0.00005以上就很接近整数// Parameter: double doubleValue    要判断的double值// Parameter: double epsilon        判断的精度，0 < epsilon < 0.5// Parameter: INT32 & intValue      如果接近，返回最接近的整数值// Returns:   bool                  接近返回true，否则返回false//************************************static bool IsInt(double doubleValue, double epsilon, INT32 &intValue);//************************************// Method:    Sign// Access:    public// Describe:  获取value的符号// Parameter: T value   要获取符号的值// Returns:   INT32     正数、0和负数分别返回1、0和-1//************************************template <typename T>static INT32 Sign(T value);const static UINT32 MIN_PRIMER = 2;     // 最小的素数//************************************// Method:    IsPrimer// Access:    public// Describe:  判断一个数是否是素数// Parameter: UINT32 num    要判断的数// Returns:   bool          是素数返回true，否则返回false//************************************static bool IsPrimer(UINT32 num);//************************************// Method:    IsIntegerSquare// Access:    public static// Describe:  判断给定的数开平方后是否为整数// Parameter: UINT32 num// Returns:   bool//************************************static bool IsIntegerSquare(UINT32 num);//************************************// Method:    GetDiffPrimerFactorNum// Access:    public static// Describe:  获取num所有的不同质因数// Parameter: UINT32 num// Returns:   set<UINT32>//************************************static set<UINT32> MoonMath::GetDiffPrimerFactorNum(UINT32 num);
};


#include "MoonMath.h"
#include <cmath>MoonMath::MoonMath(void)
{
}MoonMath::~MoonMath(void)
{
}template <typename T>
INT32 MoonMath::Sign(T value)
{if(value > 0){return 1;}else if(value == 0){return 0;}else{return -1;}
}bool MoonMath::IsInt(double doubleValue, double epsilon, INT32 &intValue)
{if(epsilon > 0.5 || epsilon < 0){return false;}if(INT32(doubleValue + epsilon) == INT32(doubleValue - epsilon)){return false;}INT32 value = INT32(doubleValue);intValue = (fabs(doubleValue - value) > 0.5) ? (value + MoonMath::Sign(doubleValue)) : (value) ;return true;
}bool MoonMath::IsPrimer(UINT32 num)
{if(num < MIN_PRIMER){return false;}UINT32 sqrtOfNum = (UINT32)sqrt((double)num); // num的2次方// 从MIN_PRIMER到sqrt(num)，如果任何数都不能被num整除，num是素数，否则不是for(UINT32 i = MIN_PRIMER; i <= sqrtOfNum; ++i){if(num % i == 0){return false;}}return true;
}bool MoonMath::IsIntegerSquare(UINT32 num)
{UINT32 qurtNum = (UINT32)sqrt((double)num);return (qurtNum * qurtNum) == num;
}set<UINT32> MoonMath::GetDiffPrimerFactorNum(UINT32 num)
{UINT32 halfNum = num / 2;set<UINT32> factors;for(UINT32 i = 2; i <= halfNum; ++i){if(!MoonMath::IsPrimer(i)){continue;}if(num % i == 0){factors.insert(i);while(num % i == 0){num /= i;}}}return factors;
}



// Consecutive prime sum
//     Problem 50
//     The prime 41, can be written as the sum of six consecutive primes:
//
// 41 = 2 + 3 + 5 + 7 + 11 + 13
//     This is the longest sum of consecutive primes that adds to a prime below one-hundred.
//
//     The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
//
//     Which prime, below one-million, can be written as the sum of the most consecutive primes?#include <iostream>
#include <windows.h>
#include <ctime>
#include <assert.h>#include <vector>
#include <MoonMath.h>using namespace std;// 打印时间等相关信息
class DetailPrinter
{
public:void Start();void End();DetailPrinter();private:LARGE_INTEGER timeStart;LARGE_INTEGER timeEnd;LARGE_INTEGER freq;
};DetailPrinter::DetailPrinter()
{QueryPerformanceFrequency(&freq);
}//************************************
// Method:    Start
// Access:    public
// Describe:  执行每个方法前调用
// Returns:   void
//************************************
void DetailPrinter::Start()
{QueryPerformanceCounter(&timeStart);
}//************************************
// Method:    End
// Access:    public
// Describe:  执行每个方法后调用
// Returns:   void
//************************************
void DetailPrinter::End()
{QueryPerformanceCounter(&timeEnd);cout << "Total Milliseconds is " << (double)(timeEnd.QuadPart - timeStart.QuadPart) * 1000 / freq.QuadPart << endl;const char BEEP_CHAR = '\007';cout << endl << "By GodMoon" << endl << __TIMESTAMP__ << BEEP_CHAR << endl;system("pause");
}/*************************解题开始*********************************///************************************
// Method:    MakePrimerVector
// Access:    public
// Describe:  获取[0,maxNum]的所有素数，存入primers
// Parameter: UINT32 maxNum             要找的最大值
// Parameter: vector<UINT32> & primers  输出素数数组，素数由小到大排列
// Returns:   void
//************************************
void MakePrimerVector(UINT32 maxNum, vector<UINT32> &primers)
{for(UINT32 num = MoonMath::MIN_PRIMER; num <= maxNum; ++num){if(MoonMath::IsPrimer(num)){primers.push_back(num);}}
}//************************************
// Method:    GetSum
// Access:    public
// Describe:  计算迭代器[itBegin,itEnd)的和
// Parameter: const vector<UINT32>::const_iterator & itBegin
// Parameter: const vector<UINT32>::const_iterator & itEnd
// Returns:   UINT32
//************************************
UINT64 GetSum(const vector<UINT32>::const_iterator &itBegin,const vector<UINT32>::const_iterator &itEnd)
{UINT64 sum = 0;for(vector<UINT32>::const_iterator it = itBegin; it != itEnd; ++it){sum += *it;}return sum;
}void TestFun1()
{cout << "Test OK!" << endl;
}void F1()
{cout << "void F1()" << endl;// TestFun1();DetailPrinter detailPrinter;detailPrinter.Start();/*********************************算法开始*******************************/const UINT32 MAX_NUM = 1000000;vector<UINT32> primers;MakePrimerVector(MAX_NUM - 1, primers);UINT32 count = primers.size();UINT64 currSum = 0;bool notFound = true;vector<UINT32>::const_iterator itBegin; // 数列的第一个数vector<UINT32>::const_iterator itEnd;   // 数列的最后一个数的下一个元素！itBegin = primers.begin();// numCount为数列中的数字个数for(UINT32 numCount = count; numCount > 0 && notFound; --numCount){itEnd = itBegin + numCount;// 获取第一组数列，索引范围[0,numCount-1]currSum = GetSum(itBegin, itEnd);if(currSum < MAX_NUM && MoonMath::IsPrimer(currSum)){break;}UINT32 remainSetCount = count - numCount;   // 剩余的数列个数for(UINT32 setIndex = 0; setIndex < remainSetCount; ++setIndex){// 计算下一组数列和，减去前一个数，加上后一个数currSum = currSum - primers[setIndex] + primers[setIndex + numCount];if(currSum < MAX_NUM && MoonMath::IsPrimer(currSum)){itBegin += setIndex + 1;itEnd += setIndex + 1;notFound = false;break;}}}cout << currSum << " is sum of " << *itBegin << " to " << *(itEnd - 1) << endl;cout<<"sum is "<<GetSum(itBegin,itEnd)<<endl;/*********************************算法结束*******************************/detailPrinter.End();
}//主函数
int main()
{F1();return 0;
}/*
void F1()
997651 is sum of 7 to 3931
sum is 997651
Total Milliseconds is 1.60107e+006
*/


这篇关于【ProjectEuler】ProjectEuler_050（找到100万以内最多连续素数的和，它也同时是个素数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/780133。

相关文章

poj2406（连续重复子串）

poj2406（连续重复子串）

题意:判断串s是不是str^n，求str的最大长度。 解题思路：kmp可解，后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后，自动跳转到next[i]，所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下； #include<iostream>#include<algorithm>#include<stdio.h>#include<math.
阅读更多...
XTU 1233 n个硬币连续m个正面个数（dp）

XTU 1233 n个硬币连续m个正面个数（dp）

题面： Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o
阅读更多...
【LeetCode热题100】前缀和

【LeetCode热题100】前缀和

这篇博客共记录了8道前缀和算法相关的题目，分别是：【模版】前缀和、【模版】二维前缀和、寻找数组的中心下标、除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和。 #include <iostream>#include <vector>using namespace std;int main() {//1. 读取数据int n = 0, q = 0;ci
阅读更多...
c++习题30-求10000以内N的阶乘

c++习题30-求10000以内N的阶乘

目录 一，题目  二，思路 三，代码    一，题目  描述 求10000以内n的阶乘。 输入描述 只有一行输入，整数n（0≤n≤10000）。 输出描述 一行，即n!的值。 用例输入 1  4 用例输出 1  24   二，思路 n    n!           0    1 1    1*1=1 2    1*2=2 3    2*3=6 4
阅读更多...
牛客小白月赛100部分题解

牛客小白月赛100部分题解

比赛地址：牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>
阅读更多...
Leetcode面试经典150题-128.最长连续序列-递归版本另解

Leetcode面试经典150题-128.最长连续序列-递归版本另解

之前写过一篇这个题的，但是可能代码比较复杂，这回来个简洁版的，这个是递归版本 可以看看之前的版本，两个版本面试用哪个都保过 解法都在代码里，不懂就留言或者私信 class Solution {/**对于之前的解法，我现在提供一共更优的解，但是这种可能会比较难懂一些（思想方面）代码其实是很简洁的，总体思想如下：不需要排序直接把所有数放入map，map的key是当前数字，value是当前数开始的
阅读更多...
在二叉树中找到两个节点的最近公共祖先（基于Java）

在二叉树中找到两个节点的最近公共祖先（基于Java）

如题  题解 public int lowestCommonAncestor(TreeNode root, int o1, int o2) {//记录遍历到的每个节点的父节点。Map<Integer, Integer> parent = new HashMap<>();Queue<TreeNode> queue = new LinkedList<>();parent.put(roo
阅读更多...
牛客小白月赛100（A,B,C,D,E,F三元环计数）

牛客小白月赛100（A,B,C,D,E,F三元环计数）

比赛链接 官方讲解 这场比较简单，ABC都很签到，D是个不太裸需要预处理的 B F S BFS BFS 搜索，E是调和级数暴力枚举，F是三元环计数。三元环考的比较少，没见过可能会偏难。 A ACM中的A题 思路： 就是枚举每个边变成原来的两倍，然后看看两短边之和是否大于第三边即可。 不能只给最短边乘 2 2 2，比如 1 4 8 这组数据，也不能只给第二短边乘 2 2 2，比
阅读更多...
诺瓦星云校招嵌入式面试题及参考答案（100+面试题、10万字长文）

诺瓦星云校招嵌入式面试题及参考答案（100+面试题、10万字长文）

SPI 通信有哪些内核接口？ 在嵌入式系统中，SPI（Serial Peripheral Interface，串行外设接口）通信通常涉及以下内核接口： 时钟控制接口：用于控制 SPI 时钟的频率和相位。通过设置时钟寄存器，可以调整 SPI 通信的速度以适应不同的外设需求。数据发送和接收接口：负责将数据从主机发送到从机以及从从机接收数据到主机。这些接口通常包括数据寄存器，用于存储待发
阅读更多...
LCP 485. 最大连续 1 的个数[lleetcode -11]

LCP 485. 最大连续 1 的个数[lleetcode -11]

从今天起，我们的算法开始研究搜索，首先就是DFS深度优先搜索（depth-first seach，DFS）在搜索到一个新的节点时，立即对该新节点进行遍 历；因此遍历需要用先入后出的栈来实现，也可以通过与栈等价的递归来实现。对于树结构而言， 由于总是对新节点调用遍历，因此看起来是向着“深”的方向前进。 下面是一个一维的DFS算法 LCP 485. 最大连续 1 的个数 给定一个二进制数组 nu
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2