Eratosthenes筛选法
2024-08-25 05:11:51
说到素数，最基本的算是一百以内的那些数了。这些数在数学竟赛中常常会被用到。比如说有这样一道题：“一百以内有多少在加2后仍然是素数的素数？”11和17就是这样的素数。如果对素数很熟悉的话，就能迅速得出答案。
那么，给定一个一百以内的数，如何迅速判断它是不是素数呢？
一个最简单的方发就是“埃拉托斯特尼筛法” (Sieve of Eratosthenes)。如上图所示，给出要筛数值的范围n，找出n√以内的素数p1,p2,…,pk。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个素数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个素数5筛，把5留下，把5的倍数剔除掉；不断重复下去......。
using System;
using System.Collections.Generic;
using System.Text; namespace 产生素数
{
class PrimeGenerator
{
private static bool[] crossedOut;
private static int[] result;
public static int[] GeneratePrimeNumbers(int maxValue)
{
if (maxValue < )
{
return new int[];
}
else
{
UncrossIntegersUpTo(maxValue);
CrossOutMultiples();
PutUncrossedIntegersIntoResult();
return result;
}
} private static void PutUncrossedIntegersIntoResult()
{
result = new int[NumberOfUncrossedIntegers()];
for (int j = , i = ; i < crossedOut.Length; i++)
{
if (NotCrossed(i))
{
result[j++] = i;
}
}
} private static bool NotCrossed(int i)
{
return crossedOut[i] == false;
} private static int NumberOfUncrossedIntegers()
{
int count = ;
for(int i=;i<crossedOut.Length;i++)
{
if (NotCrossed(i))
{
count++;
}
}
return count;
} private static void CrossOutMultiples()
{
int limit = DetermineIterationLimit();
for (int i = ; i <= limit; i++)
{
if (NotCrossed(i))
{
CrossOutMultiplesOf(i);
}
}
} private static void CrossOutMultiplesOf(int i)
{
for(int multiple=*i;multiple<crossedOut.Length;multiple+=i)
{
Console.WriteLine("multiple{0} {1}", multiple,i);
crossedOut[multiple] = true;
}
} private static int DetermineIterationLimit()
{
double interationLimit = Math.Sqrt(crossedOut.Length);
return (int)interationLimit;
} private static void UncrossIntegersUpTo(int maxValue)
{
crossedOut = new bool[maxValue + ];
for (int i = ; i < crossedOut.Length; i++)
{
crossedOut[i] = false;
}
}
}
}
最新文章
- PHP中静态(static)调用非静态方法详解
- 准备学习Spring MVC
- zookeeper能做什么？
- 利用call与apply向函数传递参数
- virgo虚拟桌面
- k临近法的实现：kd树
- Android keyevent 中的各个值
- linux cd
- easyui源码翻译1.32--Droppable（放置）
- 【线段树】HDU 5493 Queue (2015 ACM/ICPC Asia Regional Hefei Online)
- url参数中有+、空格、=、%、&、#等特殊符号的处理
- HTML5数组方法
- 童话故事 --- 什么是SQL Server Browser
- Unity3D性能优化最佳实践（四）资源审查
- 配置mysql5.5主从复制、半同步复制、主主复制
- Educational Codeforces Round 26 E - Vasya's Function
- Nginx range filter模块数字错误漏洞修复 (Nginx平滑升级)
- Javascript系列：总体理解
- Spring框架之什么是IOC的功能？
- CI/CD系列