https://stackoverflow.com/questions/1510124
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我想找总理之间的数字在0和一个漫长的变量，但我不能获得任何产出。
该节目是
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication16
{
class Program
{
void prime_num(long num)
{
bool isPrime = true;
for (int i = 0; i <= num; i++)
{
for (int j = 2; j <= num; j++)
{
if (i != j && i % j == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
{
Console.WriteLine ( "Prime:" + i );
}
isPrime = true;
}
}
static void Main(string[] args)
{
Program p = new Program();
p.prime_num (999999999999999L);
Console.ReadLine();
}
}
}
任何一个可以帮我找到什么是可能存在的错误的程序？
解决方案
可以做得更快在一个（长）线使用的接近最优试除法筛这样的：
Enumerable.Range(0, Math.Floor(2.52*Math.Sqrt(num)/Math.Log(num))).Aggregate(
Enumerable.Range(2, num-1).ToList(),
(result, index) => {
var bp = result[index]; var sqr = bp * bp;
result.RemoveAll(i => i >= sqr && i % bp == 0);
return result;
}
);
这里用于素数的数目的近似式是 π(x) < 1.26 x / ln(x) 。我们只需要通过质数来测试不超过的 x = sqrt(num) 的。
其他提示
尝试这种情况：
void prime_num(long num)
{
// bool isPrime = true;
for (long i = 0; i <= num; i++)
{
bool isPrime = true; // Move initialization to here
for (long j = 2; j < i; j++) // you actually only need to check up to sqrt(i)
{
if (i % j == 0) // you don't need the first condition
{
isPrime = false;
break;
}
}
if (isPrime)
{
Console.WriteLine ( "Prime:" + i );
}
// isPrime = true;
}
}
您只需要向上检查奇数除数的数的平方根。换句话说，你的内环需要开始：
for (int j = 3; j <= Math.Sqrt(i); j+=2) { ... }
您也可以，只要你找的数量不是素数打出来的功能，你不需要检查任何更多的除数（我看你已经这样做！）。
此如果num大于二才有效。
否的Sqrt
可以通过保持运行总和完全避免的Sqrt。例如：
int square_sum=1;
for (int j=3; square_sum<i; square_sum+=4*(j++-1)) {...}
这是因为数字（7 + 9）的总和1+（3 + 5）+会给你奇数平方的序列（1,9,25等）。因此j表示square_sum的平方根。只要square_sum小于i然后j小于所述平方根。
人们已经提到的一对夫妇的构建模块朝这样做的高效率地，但没人真的把碎片在一起。的 筛埃拉托塞尼 是一个良好的开端，但是有了它，你会跑出去的记忆 长 在你达到极限，你设置的。这并不意味着它是无用的，虽然-当你在做你的循环，你真正关心的主要因子。因此，你可以开始通过使用筛创建一个基地的总数，然后使用那些在循环测试的数字为主导地位。
当你写的循环，但是，您真的不想我们sqrt(i)在环条件下为几个答案的建议。你和我知道的sqrt是"纯粹的"功能总是提供同样的回答，如果给予相同的输入参数。不幸的是，编译器不知道，所以，如果使用类似'<=数学。sqrt(x)'在循环的条件，它将重新计算sqrt的数量的每一次迭代的循环。
你可以避免的那几个不同的方式。你可以预算的sqrt前的循环，并使用预算的价值在循环的条件，或者你可以在工作的其他方向，并改变 i<Math.sqrt(x) 要 i*i<x.就个人而言，我预计算的平方根虽然--我认为这是清楚的和可能更快一点--但是这取决于数量的迭代循环(的 i*i 意味着它仍然是这样做的一个倍增中的循环)。只有几次迭代， i*i 通常将会以更快。有足够的迭代，损失 i*i 每一次迭代超过了时间用于执行 sqrt 一旦以外的循环。
这可能是足够的大小的数字，你可以处理--有15位数的限制装置的平方根是7或8位数，这符合在很合理数量的存储器。另一方面，如果要处理的数字，在这个范围很多，你可能会想看看一些更先进的黄金-检查的算法，例如 波拉德或伦的算法.这些都是更复杂的(说得客气一点)，但一个 很多 快大的数字。
还有其他算法进行甚至更大的数字(二次筛, 一般数域筛)但是，我们不会得到他们的时刻--他们是更多复杂的，真正仅仅用于处理非常大的数字(对金纳米花开始被用于100多位数范围)。
<强>第一步：写的扩展方法，以找出是否一个输入是素数
public static bool isPrime(this int number ) {
for (int i = 2; i < number; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
<强> 2步骤写，将打印所有素数是0和之间的方法的数目的输入
public static void getAllPrimes(int number)
{
for (int i = 0; i < number; i++)
{
if (i.isPrime()) Console.WriteLine(i);
}
}
这可能只是我的意见，但还有另外一个严重的错误，在你的程序（撇开给“素数”的问题，它已被彻底回答）。
像应答的其余部分，我假设这是功课，这表明你想成为一名开发人员（大概）。
您需要学会如何划分你的代码。这不是你总是需要在一个项目做，但它的好，知道如何做到这一点。
您方法prime_num（长NUM）可以站在一个更好，更描述性名称。如果它应该找到一个比一个给定数量减去所有质数，它应该返回他们的名单。这使得它更容易单独的显示器和你的功能。
如果它只是返回一个包含素数，那么你可以在你的主要功能显示出来（可能调用另一个外功能相当打印出来），或在进一步计算的路线中使用它们。一个IList
所以，我给你最好的建议是，做这样的事情：
public void main(string args[])
{
//Get the number you want to use as input
long x = number;//'number' can be hard coded or retrieved from ReadLine() or from the given arguments
IList<long> primes = FindSmallerPrimes(number);
DisplayPrimes(primes);
}
public IList<long> FindSmallerPrimes(long largestNumber)
{
List<long> returnList = new List<long>();
//Find the primes, using a method as described by another answer, add them to returnList
return returnList;
}
public void DisplayPrimes(IList<long> primes)
{
foreach(long l in primes)
{
Console.WriteLine ( "Prime:" + l.ToString() );
}
}
即使你最终地方工作在不需要speration这样的，它的好，知道如何做到这一点。
EDIT_ADD：如果威尔尼斯是正确的，这个问题的目的只是为了输出素数的，只要运行该程序（按暂停连续流/休息暂停和启动任意键再次）与每一个获得该上限没有严重的希望，那么代码应与无上限的说法和“真”为先“我”的循环范围检查写入。在另一方面，如果这个问题要实际打印的素数高达限制，则下面的代码将做的工作更有效地利用审判庭只为奇数，与它不使用内存在的所有优势（它也可以被转换为连续的环按照上述）：
static void primesttt(ulong top_number) {
Console.WriteLine("Prime: 2");
for (var i = 3UL; i <= top_number; i += 2) {
var isPrime = true;
for (uint j = 3u, lim = (uint)Math.Sqrt((double)i); j <= lim; j += 2) {
if (i % j == 0) {
isPrime = false;
break;
}
}
if (isPrime) Console.WriteLine("Prime: {0} ", i);
}
}
首先，问题代码不产生输出，因为，它的循环变量是整数，并且测试的极限是一个巨大的长整数，这意味着它是不可能的循环来达到产生一个内部循环限制的编辑： 由此可变“J”循环返回到周围负数;当“J”可变回来周围为-1，所测试的号码失败的首要测试，因为所有数值整除-1的 END_EDIT 即可。即使这是纠正，问题的代码产生很慢的输出，因为它被束缚了由全范围的数字高达除此之外做得非常大量的合数（所有的偶数加上奇复合材料）的64位部门十数提高到了它可以产生可能每一个素的16次方。上面的代码有效，因为它限制了计算，以仅奇数和只做模分割到平方根的当前数目的被测试
这需要一个小时左右，以达到显示的素数到十亿，因此可以想见的时间，将采取的所有素数显示到10000兆（10升高到16次方）的量，特别是当计算得到随范围慢。的 END_EDIT_ADD
虽然使用LINQ的作品，它是不是真的埃拉托色尼的筛，因为它是的审判庭时，未优化的，因为它不能消除奇素数，不会在发现碱素的平方启动，并且不停止对灭杀碱素数比的平方根的顶部数的筛大。它也相当慢，由于多个嵌套枚举操作。
它实际上是LINQ的聚合方法的滥用和不能有效地使用第一的生成的两个LINQ的范围的。它可以如下成为优化的审判司以更少的开销枚举：
static IEnumerable<int> primes(uint top_number) {
var cullbf = Enumerable.Range(2, (int)top_number).ToList();
for (int i = 0; i < cullbf.Count; i++) {
var bp = cullbf[i]; var sqr = bp * bp; if (sqr > top_number) break;
cullbf.RemoveAll(c => c >= sqr && c % bp == 0);
} return cullbf; }
它运行快许多倍比SLaks回答。然而，它仍然是缓慢和内存密集型由于列表生成和多枚举以及多个除法（由模暗示）操作。
埃拉托塞尼执行以下真筛运行快约30倍和花费较少的存储器，因为它仅使用每筛分数一个比特表示和限制了其枚举到最终迭代序列输出，以及仅具有治疗的最佳化奇复合材料，以及只有从基质数的平方为基础素数至最大数的平方根剔除，如下所示：
static IEnumerable<uint> primes(uint top_number) {
if (top_number < 2u) yield break;
yield return 2u; if (top_number < 3u) yield break;
var BFLMT = (top_number - 3u) / 2u;
var SQRTLMT = ((uint)(Math.Sqrt((double)top_number)) - 3u) / 2u;
var buf = new BitArray((int)BFLMT + 1,true);
for (var i = 0u; i <= BFLMT; ++i) if (buf[(int)i]) {
var p = 3u + i + i; if (i <= SQRTLMT) {
for (var j = (p * p - 3u) / 2u; j <= BFLMT; j += p)
buf[(int)j] = false; } yield return p; } }
在上面的代码计算所有素数千万的范围中的Intel i7-2700K（3.5千兆赫）。
约77毫秒要么的两个静态方法可以调用和测试与使用语句和与静态主方法如下：
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
static void Main(string[] args) {
Console.WriteLine("This program generates prime sequences.\r\n");
var n = 10000000u;
var elpsd = -DateTime.Now.Ticks;
var count = 0; var lastp = 0u;
foreach (var p in primes(n)) { if (p > n) break; ++count; lastp = (uint)p; }
elpsd += DateTime.Now.Ticks;
Console.WriteLine(
"{0} primes found <= {1}; the last one is {2} in {3} milliseconds.",
count, n, lastp,elpsd / 10000);
Console.Write("\r\nPress any key to exit:");
Console.ReadKey(true);
Console.WriteLine();
}
，它会显示质数的序列中的数量最多为极限，拉ST素中发现，并且在枚举远的时间消耗。
<强> EDIT_ADD：然而，为了生产的素数小于10000兆（10到16次方）的数的枚举作为问题询问，一个分段的寻呼方法使用多芯需要处理，但即使有C ++和非常高度优化PrimeSieve ，这将需要的东西超过400小时，只是生产中发现的素数的数量，以及数十倍，长期对所有这些枚举所以在做了一年的问题问什么。要使用未优化的审判庭算法试图做到这一点，它会采取超亿万和一个非常非常长的时间，即使使用优化的审判庭算法在像十去其第两百万功率年（即两百万零年！ ！）。
这是没有太大的疑问，他的台式机只是坐了一停顿时，他试了一下!!!!如果他曾试图一个较小的范围，例如一百万，他仍然会发现它需要在几秒钟的范围内实施。
我在这里发布的解决方案，将不会削减它无论是作为甚至一个埃拉托色尼的最后筛将需要约640 TB的内存，以便范围。
这就是为什么作为对所有用户只指定页面分割方法如PrimeSieve可以处理这类的范围问题，甚至还需要一个很长的时间，在几周到几年除非有访问超级计算机拥有数十万个内核。的 END_EDIT_ADD
闻起来像更多的家庭作业。我非常非常老的图形计算器有一个是这样的首要计划。 Technnically内等分检查环路仅需要运行至i ^（1/2）。你需要找到0和L之间的“所有”质数？另一个主要问题是，你的循环变量是“诠释”，而你输入的数据是“长”，这将导致溢出使您的循环不甚至执行一次。固定循环变量。
在C＃一行代码： -
Console.WriteLine(String.Join(Environment.NewLine,
Enumerable.Range(2, 300)
.Where(n => Enumerable.Range(2, (int)Math.Sqrt(n) - 1)
.All(nn => n % nn != 0)).ToArray()));
在
private static IEnumerable Primes01(int num)
{
return Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num))))
.Aggregate(Enumerable.Range(1, num).ToList(),
(result, index) =>
{
result.RemoveAll(i => i > result[index] && i%result[index] == 0);
return result;
}
);
}
聚集体的种子应范围为1〜NUM因为这个列表将包含的素数的最终列表。所述Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num))))是时代的种子被清除的数量。
ExchangeCore论坛有很好的控制台应用程序列出看起来发现素数写入一个文件，它看起来像你也可以使用相同的文件作为出发点，因此您不必重新从2发现的素数，他们提供了一个下载该文件的所有发现素数高达1亿所以这将是一个好的开端。
在页上的算法也需要几个快捷方式（奇数和只检查最多的平方根），这使得它非常有效的，它可以让你计算长的数字。
所以这基本上是只有两个错别字，一个最不幸的，for (int j = 2; j <= num; j++)这是1%2,1%3 ... 1%(10^15-1)的非生产性测试肚里上很长的时间，因此OP没有获得的理由< EM> “任何输出”。的应该已经j < i;代替另外，次要一个相比较，是，i应该从2开始，而不是从0：
for( i=2; i <= num; i++ )
{
for( j=2; j < i; j++ ) // j <= sqrt(i) is really enough
....
当然，它不能合理预期的控制台280000个亿素数或如此印出来的的在任何合理的时间框架内完成。所以，这个问题的初衷显然是打印出的素数源源不断，无限期。因此，所有建议使用简单埃拉托色尼筛的解决方案是完全没有道理在这里，因为简单的埃拉托色尼筛是有界的 - 限制必须提前设定。
有什么能在这里工作是优化审判庭这将节省的素数，因为它发现他们，并测试对素数，而不仅仅是候选下的所有号码。
第二替代方案中，与更好的复杂性（即，更快）是使用埃拉托塞尼的的分段的筛 。这是增量和无界的。
这两种方案将使用双阶生产的素数的：一个将产生并保存素数，通过在测试（或筛分）的其它阶段使用，远高于的极限第一阶段（其当然平方以下 - 自动延伸的第一阶段中，作为第二阶段将更进一步，进一步向上）。
要坦率地说，有些建议的解决方案是很慢的，因此是不好的建议。为了测试一个数字是素数，你需要一些分/模运算，但计算范围，你不必。
基本上你只是排除是发现较早素数的倍数的数字，作为顷（根据定义）不素数本身。
我不会放弃的全面实施，这将是容易的，这是伪代码的方法。 （在我的机器，实际执行计算在8秒内的Sytem.Int32（2 bilion）所有素数。
public IEnumerable<long> GetPrimes(long max)
{
// we safe the result set in an array of bytes.
var buffer = new byte[long >> 4];
// 1 is not a prime.
buffer[0] = 1;
var iMax = (long)Math.Sqrt(max);
for(long i = 3; i <= iMax; i +=2 )
{
// find the index in the buffer
var index = i >> 4;
// find the bit of the buffer.
var bit = (i >> 1) & 7;
// A not set bit means: prime
if((buffer[index] & (1 << bit)) == 0)
{
var step = i << 2;
while(step < max)
{
// find position in the buffer to write bits that represent number that are not prime.
}
}
// 2 is not in the buffer.
yield return 2;
// loop through buffer and yield return odd primes too.
}
}
在解决方案需要按位操作的一个很好的理解。但它的方式，以及如何更快。您也可以安全的盘胜负的结果，如果你需要他们以备后用。 17 * 10 ^ 9号的结果可以用1 GB被萨法德，并且该结果集的计算需要最多约2分钟。
我知道这是老安静的问题，但在这里读书后： 的筛埃拉托塞尼维基
这是我的方式写的从理解算法：
void SieveOfEratosthenes(int n)
{
bool[] primes = new bool[n + 1];
for (int i = 0; i < n; i++)
primes[i] = true;
for (int i = 2; i * i <= n; i++)
if (primes[i])
for (int j = i * 2; j <= n; j += i)
primes[j] = false;
for (int i = 2; i <= n; i++)
if (primes[i]) Console.Write(i + " ");
}
在第一循环中，我们填充布尔阵列与真实的。
第二个for循环将从2，因为1不是素数就会检查是否素数仍然没有改变，然后分配假到j的索引。
最后一个循环，我们只是在印刷时是素数。
非常相似的 - 从练习实施埃拉托塞尼的筛在C＃：
public class PrimeFinder
{
readonly List<long> _primes = new List<long>();
public PrimeFinder(long seed)
{
CalcPrimes(seed);
}
public List<long> Primes { get { return _primes; } }
private void CalcPrimes(long maxValue)
{
for (int checkValue = 3; checkValue <= maxValue; checkValue += 2)
{
if (IsPrime(checkValue))
{
_primes.Add(checkValue);
}
}
}
private bool IsPrime(long checkValue)
{
bool isPrime = true;
foreach (long prime in _primes)
{
if ((checkValue % prime) == 0 && prime <= Math.Sqrt(checkValue))
{
isPrime = false;
break;
}
}
return isPrime;
}
}
素助手非常快的计算
public static class PrimeHelper
{
public static IEnumerable<Int32> FindPrimes(Int32 maxNumber)
{
return (new PrimesInt32(maxNumber));
}
public static IEnumerable<Int32> FindPrimes(Int32 minNumber, Int32 maxNumber)
{
return FindPrimes(maxNumber).Where(pn => pn >= minNumber);
}
public static bool IsPrime(this Int64 number)
{
if (number < 2)
return false;
else if (number < 4 )
return true;
var limit = (Int32)System.Math.Sqrt(number) + 1;
var foundPrimes = new PrimesInt32(limit);
return !foundPrimes.IsDivisible(number);
}
public static bool IsPrime(this Int32 number)
{
return IsPrime(Convert.ToInt64(number));
}
public static bool IsPrime(this Int16 number)
{
return IsPrime(Convert.ToInt64(number));
}
public static bool IsPrime(this byte number)
{
return IsPrime(Convert.ToInt64(number));
}
}
public class PrimesInt32 : IEnumerable<Int32>
{
private Int32 limit;
private BitArray numbers;
public PrimesInt32(Int32 limit)
{
if (limit < 2)
throw new Exception("Prime numbers not found.");
startTime = DateTime.Now;
calculateTime = startTime - startTime;
this.limit = limit;
try { findPrimes(); } catch{/*Overflows or Out of Memory*/}
calculateTime = DateTime.Now - startTime;
}
private void findPrimes()
{
/*
The Sieve Algorithm
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
*/
numbers = new BitArray(limit, true);
for (Int32 i = 2; i < limit; i++)
if (numbers[i])
for (Int32 j = i * 2; j < limit; j += i)
numbers[j] = false;
}
public IEnumerator<Int32> GetEnumerator()
{
for (Int32 i = 2; i < 3; i++)
if (numbers[i])
yield return i;
if (limit > 2)
for (Int32 i = 3; i < limit; i += 2)
if (numbers[i])
yield return i;
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
// Extended for Int64
public bool IsDivisible(Int64 number)
{
var sqrt = System.Math.Sqrt(number);
foreach (var prime in this)
{
if (prime > sqrt)
break;
if (number % prime == 0)
{
DivisibleBy = prime;
return true;
}
}
return false;
}
private static DateTime startTime;
private static TimeSpan calculateTime;
public static TimeSpan CalculateTime { get { return calculateTime; } }
public Int32 DivisibleBy { get; set; }
}
public static void Main()
{
Console.WriteLine("enter the number");
int i = int.Parse(Console.ReadLine());
for (int j = 2; j <= i; j++)
{
for (int k = 2; k <= i; k++)
{
if (j == k)
{
Console.WriteLine("{0}is prime", j);
break;
}
else if (j % k == 0)
{
break;
}
}
}
Console.ReadLine();
}
static void Main(string[] args)
{ int i,j;
Console.WriteLine("prime no between 1 to 100");
for (i = 2; i <= 100; i++)
{
int count = 0;
for (j = 1; j <= i; j++)
{
if (i % j == 0)
{ count=count+1; }
}
if ( count <= 2)
{ Console.WriteLine(i); }
}
Console.ReadKey();
}
U可以正常使用的素数概念必须仅两个因素（一个和本身）。 所以，做这样的，简单的方法
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace PrimeNUmber
{
class Program
{
static void FindPrimeNumber(long num)
{
for (long i = 1; i <= num; i++)
{
int totalFactors = 0;
for (int j = 1; j <= i; j++)
{
if (i % j == 0)
{
totalFactors = totalFactors + 1;
}
}
if (totalFactors == 2)
{
Console.WriteLine(i);
}
}
}
static void Main(string[] args)
{
long num;
Console.WriteLine("Enter any value");
num = Convert.ToInt64(Console.ReadLine());
FindPrimeNumber(num);
Console.ReadLine();
}
}
}
此溶液显示为0和100之间的所有素数
int counter = 0;
for (int c = 0; c <= 100; c++)
{
counter = 0;
for (int i = 1; i <= c; i++)
{
if (c % i == 0)
{ counter++; }
}
if (counter == 2)
{ Console.Write(c + " "); }
}
这是在C＃以计算素数的最快方式。
void PrimeNumber(long number)
{
bool IsprimeNumber = true;
long value = Convert.ToInt32(Math.Sqrt(number));
if (number % 2 == 0)
{
IsprimeNumber = false;
}
for (long i = 3; i <= value; i=i+2)
{
if (number % i == 0)
{
// MessageBox.Show("It is divisible by" + i);
IsprimeNumber = false;
break;
}
}
if (IsprimeNumber)
{
MessageBox.Show("Yes Prime Number");
}
else
{
MessageBox.Show("No It is not a Prime NUmber");
}
}
class CheckIfPrime
{
static void Main()
{
while (true)
{
Console.Write("Enter a number: ");
decimal a = decimal.Parse(Console.ReadLine());
decimal[] k = new decimal[int.Parse(a.ToString())];
decimal p = 0;
for (int i = 2; i < a; i++)
{
if (a % i != 0)
{
p += i;
k[i] = i;
}
else
p += i;
}
if (p == k.Sum())
{ Console.WriteLine ("{0} is prime!", a);}
else
{Console.WriteLine("{0} is NOT prime", a);}
}
}
}
有实现算法的一些非常最佳方式。但是，如果你不知道很多关于数学，你只需按照黄金作为需求的定义： 一个数字，由1和本身（而不是其他）是唯一整除，这里有一个简单的了解代码为正数。
public bool IsPrime(int candidateNumber)
{
int fromNumber = 2;
int toNumber = candidateNumber - 1;
while(fromNumber <= toNumber)
{
bool isDivisible = candidateNumber % fromNumber == 0;
if (isDivisible)
{
return false;
}
fromNumber++;
}
return true;
}
由于每个数为整除1和由本身，我们开始从2检查起直到即将本身之前的数目。这是基本的推理。
您也可以做到这一点：
class Program
{
static void Main(string[] args)
{
long numberToTest = 350124;
bool isPrime = NumberIsPrime(numberToTest);
Console.WriteLine(string.Format("Number {0} is prime? {1}", numberToTest, isPrime));
Console.ReadLine();
}
private static bool NumberIsPrime(long n)
{
bool retVal = true;
if (n <= 3)
{
retVal = n > 1;
} else if (n % 2 == 0 || n % 3 == 0)
{
retVal = false;
}
int i = 5;
while (i * i <= n)
{
if (n % i == 0 || n % (i + 2) == 0)
{
retVal = false;
}
i += 6;
}
return retVal;
}
}
