算法-素数表

it2025-12-08 18

算法-素数表_埃氏筛选法

问题概述1. 问题分析1.1 算法核心 2. 解决方案3. 资源分享

问题概述

题目：素数表_埃氏筛选法问题描述：在很多算法题中都会涉及到素数的使用，因此如何快速高效地求素数是我们程序猿必不可少的能力。

输入：输入有多组数据。每组一行，输入n。输出：输出所有从1到这个整数之间(不包括1和这个整数) 个位为1的素数(素数之间用空格隔开，最后一个素数后面没有空格)，如果没有则输出-1 样例输入： 70 样例输出： 11 31 41 61

1. 问题分析

一般说到求素数表，我们首先想到的是枚举所有可能的数，然后对每一个可能的数进行素数判断，那什么叫素数呢？若一个数只能被自己以及数字1整除，那么这个数就叫素数，或质数; 也就是说我们要对每一个可能的数字进行连续求余运算，若在数字2-这个数-1之间出现了能够整除的因子，那么这个数就不是素数，反之就是素数，这个一重嵌套循环的算法时间复杂度是On²；仔细思考这个过程会发现，有很多重复计算的过程，比如2是第一个素数，12是2的倍数，那么其实所有整除的因子中有2的数都不是素数了，因为他们都有一个整除的因子是2，因而后续素数判断的时候不应该再浪费时间去判断这些数了，所以这个时候就有了新的算法-埃氏筛选法；本题还要多做一步处理就是，最后只输出个位为1的素数，所以对每一个素数要追加处理，若个位为1则加入我们的结果数组，这样便于后续题目输出；

1.1 算法核心

埃氏筛选法：给出要筛数值的范围n，找出根号n以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去…; 也就是说，我们需要声明一个容量较大的数组来做素数表，一个相同容量的标志数组做状态表，每次找到素数就把它存储至素数表中，然后把它的标志位设置为true，表示已经枚举过这个数字了，接着把它的倍数筛了，筛选边界是数字2-根号n;

2. 解决方案

#include <iostream> #include <vector> using namespace std; #define maxLength 100010 /* 算法题目：素数问题描述：输入一个整数n(2<=n<=10000)，要求输出所有从1到这个整数之间(不包括1和这个整数)个位为1的素数，如果没有则输出-1 输入：输入有多组数据。每组一行，输入n。输出：输出所有从1到这个整数之间(不包括1和这个整数) 个位为1的素数(素数之间用空格隔开，最后一个素数后面没有空格)，如果没有则输出-1 样例输入： 70 样例输出： 11 31 41 61 */ int n, tmp = 2, t; bool primeSign[maxLength] = { 0 }; vector<int> result, primeTable; void findPrimeTable(); int main() { while (scanf("%d", &n) != EOF) { findPrimeTable(); if(result.size() == 0) printf("-1\n"); for (int i = 0; i < result.size() && result[i] < n; i++) { if(result[i + 1] >= n) { printf("%d\n", result[i]); break; } if(i + 1 == result.size()) printf("%d\n", result[i]); else printf("%d ", result[i]); } } return 0; } void findPrimeTable() { for (int i = tmp; i < maxLength; i++) { if (primeSign[i] == false) { if (i >= n) { tmp = i; break; } primeTable.push_back(i); for (int j = i + i; j < maxLength; j += i) primeSign[j] = true; t = i % 10; if(t == 1) result.push_back(i); } } }

3. 资源分享

旗木白哉のGitHub： https://github.com/YangMengHeng C++ / C源代码下载地址： https://github.com/YangMengHeng/myCode/tree/master/VSCode Java源代码下载地址： https://github.com/YangMengHeng/myCode/tree/master/Java 旗木白哉のblog源代码下载地址： https://github.com/YangMengHeng/myCode/tree/master/%E6%97%97%E6%9C%A8%E7%99%BD%E5%93%89%E3%81%AEblog

最新回复(0)