| 等 级 | |
| 排 名 | 633 |
| 经 验 | 3965 |
| 参赛次数 | 0 |
| 文章发表 | 16 |
| 年 龄 | 0 |
| 在职情况 | 学生 |
| 学 校 | tjnu |
| 专 业 |
自我简介：
TA的其他文章
| C二级辅导-求偶数和 （C语言代码）（不用数组） 浏览：343 |
| 用筛法求之N内的素数。 （C语言代码）筛求法+优化普通方法 浏览：13491 |
原题链接：用筛法求之N内的素数
解题思路:
定义一个数组prime[],赋初值为0，数组下表对应这个数字，通过数组值来判断是否为素数
ex:
prime[2]==0 表示2为素数 prime[8]==1 表示8不为素数
根据算术基本定理：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积
所以若prime[i]==0,则prime[i*j]==1 即prime[i*j]不为素数
只要i：2->n 即可构建n以内的质数表
注意事项:
prime[0]=prime[1]=1; //0 1特殊处理
参考代码:
#include<stdio.h>
int main(){
int prime[10000]={0};
int i,j;
int n;
scanf("%d",&n);
prime[0]=prime[1]=1;
for(i=2;i<n;i++)
if(prime[i]==0)
for(j=2;i*j<=n;j++)
prime[i*j]=1;
for(i=0;i<n;i++)
if(prime[i]==0)
printf("%d\n",i);
return 0;
}下面是另一种求素数方法，如果可以优化的话在下方留言哦~
#include<stdio.h>
#include<math.h>
void judge(int n);
//----------------------------*
int main(void){
int n,i;
scanf("%d",&n);
for(i=2;i<=n;i++)
if(i%2!=0) //去偶数
judge(i);
return 0;
}
//----------------------------*
void judge(int n){
int i,flag=0;
double sq;
sq=sqrt(n); //减少开根运算
for( i=2;i<=sq;i++) //因数都是成对存在的 而且因数对一定是一大一小（除平方根）
if(n%i==0){
flag=1;
break;
}
if(flag==0)
printf("%d\n",n);
}0.0分
77 人评分
评论区
#include <stdio.h>
#include <math.h>
int main()
{
int a[100000]={0};
int N=0;
int i=0,j=0;
scanf("%d",&N);
for(i=2;i<=(int)sqrt((double)N);i++)
{
for(j=2;j<=N;j++)
{
if(j==i)
continue;
if(j%i==0)
a[j]=1;
}
}
for(j=2;j<=N;j++)
{
if(a[j]==0)
{
printf("%d\n",j);
}
}
return 0;
}
2022-07-22 12:25:59
//简单粗暴，没有2就直接加2
#include<stdio.h>
#include<math.h>
void main()
{
int m,k,n;
int i,s=0;
scanf("%d",&n);
for(m=2;m<=n;m++)
{
k=sqrt(m);
for(i=2;i<=k;i++)
{
if(m%i==0)
break;
}
//if(i>=k+1)
if(m%i!=0)
{
printf("%d\n",m);
}
if(m==2)
{
printf("2\n");
}
}
return 0;
}
2022-03-11 22:50:42
这为啥过不了
#include <iostream>
using namespace std;
int main(void)
{
int n;
cin >> n;
int q[n]{};
for (int i = 1; i < n; i++)
{
q[i] = i+1;
if (q[i] != 2 && q[i] != 3 && q[i] != 5 && q[i] != 7)
if (q[i] % 2 == 0 || q[i] % 3 == 0 || q[i] % 5 == 0 || q[i] % 7 == 0)
{
q[i] = 0;
}
if (q[i] != 0) cout << q[i] << endl;
}
return 0;
}
2022-02-23 23:12:35
int main(){
int i;
int n;
int a,sum;
for(n=0;n<101;n++){
for(i=1;i<n;i++){
a=n%i;
if(a!=0) sum+=1;
}
if(sum==n-2) printf("%d\n",n);
sum=0;
}
return 0;
}
2022-02-03 10:38:28
#include<stdio.h>
#include<math.h>
int main()
{
int n;
int a[1000]={1,1,0};
int i,j;
scanf("%d",&n);
for(i=0;i<=n;i++)
for(j=2;j<=sqrt(i);j++)
if(i%j==0)
a[i]=1;
for(i=0;i<=n;i++)
if(a[i]==0)
printf("%d\n",i);
return 0;
}
2021-11-20 18:50:04
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
for(int m=2;m<=n;m++){
for(int p=2;p<=m;p++){
if(m==p)
cout<<m<<endl;
if(m%p==0)
break;
}
}
return 0;
}
2021-08-22 18:29:03
我这个比较简单
#include<stdio.h>
int main()
{
int i,n,r,j;
scanf("%d",&n);
for(i=2;i<=n;i++)
{
for(j=2;j<=i;j++)
{
r=i%j;
if(r==0&&j<i)
break;
if(r==0&&j==i)
printf("%d\n",i);
}
}
return 0;
}
2021-06-15 22:43:44
求问我自己运行没错误但是提交显示出错
#include<stdio.h>
const int maxn = 10001;
bool p[maxn] = {0};
int pnum = 0;
int prime[maxn];
int n;
void is_Prime(){
for(int i = 2; i<=n; i++){
if(p[i]==false){
prime[pnum++] = i;
for(int j=i*2;j<=n;j+=i){
p[j] = true;
}
}
}
}
int main(){
scanf("%d", &n);
is_Prime();
for(int i=0; i<pnum; i++){
printf("%d\n", prime[i]);
}
return 0;
}
2021-04-13 23:32:04
精彩推荐
C语言程序设计教程（第三版）课后习题8.6 （C语言代码）浏览：584 |
C语言程序设计教程（第三版）课后习题5.7 （Java代码）浏览：887 |
C语言程序设计教程（第三版）课后习题5.7 （C语言代码）浏览：677 |
淘淘的名单 （C语言代码）浏览：1100 |
WU-输出正反三角形 （C++代码）浏览：1018 |
C语言程序设计教程（第三版）课后习题6.8 （C++代码）浏览：575 |
C语言程序设计教程（第三版）课后习题6.1 （C语言代码）浏览：698 |
简单的a+b （C语言代码）浏览：596 |
最小公倍数 （C语言代码）浏览：1026 |
DNA （C语言代码）浏览：736 |