求N以内的所有素数
程序员文章站
2022-03-09 15:07:58
...
求N以内的素数
代码如下:
#include "stdafx.h"
#include"conio.h"
#include"math.h"
#include"malloc.h"
typedef long long prime;
typedef struct PN//构造素数节点
{
union
{
prime data;
long long length;
};
struct PN *next;
}PN;
static PN* ApplyNode(prime x)//申请新的结点
{
PN* s = (PN*)malloc(sizeof(PN));
if (s == NULL)
return NULL;
s->data = x;
s->next = NULL;
return s;
}
void PListInitiate(PN *head)//素数列表初始化
{
head = (PN*)malloc(sizeof(PN));
head->next = NULL;
}
bool PNInsert(PN* p, prime x)//新旧节点连接
{
if (p == NULL)
return false;
p->next = ApplyNode(x);
return true;
}
void Show(PN* head)//呈现元素内容
{
printf("%lld;\n", head->length);
PN* p = head->next;
while (p != NULL)
{
printf("%lld;\n", p->data);
p = p->next;
}
}
PN* Prime(long long N)//求N以内的素数
{
long long i, j;
long long k = 0;
long long count;
PN* head = (PN*)malloc(sizeof(PN));
PListInitiate(head);
head->length = 0;
PN* p = head;
PN* h = head;
for (i = 2; i <= floor(sqrt(N)); i++)//计算前N^1/2中含有的素数
{
for (j = 2; j <= floor(sqrt(i)); j++)
if (i%j == 0)
break;
if (j > floor(sqrt(i)))
{
PNInsert(p, i);
p = p->next;
count = i;
k++;
head->length += 1;
}
}
for (i = count + 1; i < N; i++)//计算利用爱拉托斯散筛法计算N以前的所有素数
{
long long n = 0;//利用n判断该数i是否是整除N^1/2中任意素数的倍数
h = head;
for(j = 0; j < k; j++)
{
if (i%(h->next->data) != 0)
{
h = h->next;
n++;
continue;
}
}
if (n == k)
{
PNInsert(p, i);
p = p->next;
head->length += 1;
}
}
return head;
}
int main()
{
long long N = 100000;
PN * A =Prime(N);
Show(A);
free(A);
_getch();
return 0;
}
我在这里求
100000
100000
100000以内的素数:
从运算结果可以看出
100000
100000
100000以内有9592个素数.
上一篇: 求1000以内的回文素数
下一篇: Java EE 6的依赖注入