如何在两个数字之间编写查找素数的代码 [英] How do I write a code for find prime numbers between two numbers

问题描述

我的问题是

这个程序不是

性能

我尝试过：

使用System; 
使用System.Collections.Generic; 
使用System.Linq; 
使用System.Text; 
使用System.Threading.Tasks; 
 
命名空间the_prime_number_between_a_anb_b 
 {
 class Program 
 {
 static void Main（）
 {
 int num，i，a ，b; 
 Console.Write（查找一系列数字中的素数：）; 
 Console.Write（输入起始数量范围：）; 
 a = Convert.ToInt32（Console.ReadLine（））; 
 Console.Write（输入结束数量范围：）; 
 b = Convert.ToInt32（Console.ReadLine（））; 
 Console.Write（{0}和{1}之间的素数是：\ n，a，b）; 
 
 for（num = a; num< = b; num ++）
 for（i = 2; i< = num / 2; i ++）
 {
 if（num％i == 0）
 {
 break; 
} 
}} 
 
 if（num％i！= 0）
 {
 Console.Write（{0}，num）; 
 
} 
 
} 
} 
} 

解决方案

< blockquote>首先让你的代码编译 - 这不会，因为大括号在错误的地方，把你的一些代码放在 main 方法之外。 />


不，这个程序不是性能 - 因为你一遍又一遍地重复一个潜在的大范围的数字：你检查每个数字是否在2到1,000,000范围内是素数，然后检查2到1,000,001范围内的每个数字是否为素数，然后检查2到1,000,002范围内的每个数字是否为素数，然后检查...



这非常浪费。

而不是这样做，一次计算出范围内的所有素数，然后存储它们。然后打印出来。



我？我很想永久存储它们：将素数写入文件，并在加载应用程序时将其读回 - 如果范围在文件范围内，那么您不需要再做任何工作，只需打印即可。如果不是，则生成新的素数，然后将它们添加到文件中以供下次使用。几次运行后，您的应用程序可能不需要计算大多数检查的任何素数...

您应该在内部循环的开头设置一个标志以指示该数字是一个素数。然后在 break 语句之前将其设置为 false 以表明它不是素数。然后，如果标志仍设置为 true ，则可以在循环完成后打印数字。

引用：

我的问题是

这个程序没有性能

不，你的问题是那个此程序错误，不打印任何内容！

如果您的真实程序打印出正确的结果，则在此处复制时出错。

引用：

此程序不是性能

这意味着您希望程序尽可能快，优化。这意味着您了解您的程序及其执行的原因。
第一步是阅读有关问题的文档整数分解。



你怎么知道你必须停止潜在的因素检查？

你停在num / 2，这是什么原因？

当你用手检查101的因子时，你会停在50或者你提前停止吗？

如果因为51 * 2超过num而停在50，你必须利用你已经知道2已经被检查过了，不是101的因素，也不是3 ...

当你理解了这一点并做了必要的改变后，性能会更好，但仍然不是最佳的。 />


建立一个函数 isprime 来分离关注点也是一个好主意。

my problem it is
this programm not

performance

What I have tried:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace the_prime_number_between_a_anb_b
{
    class Program
    {
        static void Main()
        {
            int num, i, a, b;
            Console.Write("Find the prime numbers within a range of numbers:");
            Console.Write("Input starting number of range: ");
            a = Convert.ToInt32(Console.ReadLine());
            Console.Write("Input ending number of range : ");
            b = Convert.ToInt32(Console.ReadLine());
            Console.Write("The prime numbers between {0} and {1} are : \n", a, b);

            for (num = a; num <= b; num++)
                for (i = 2; i <= num / 2; i++)
                {
                    if (num % i == 0)
                    {
                        break;
                    }
                } }

                if (num % i != 0)
                    {
                    Console.Write("{0}",num);
                    
            }
            
        }
    }
}

解决方案

Start by getting your code to compile - that won't, because the curly brackets are in the wrong place, putting some of your code outside the main method.

And no, that program is not "performance" - because you repeat a potentially huge range of numbers over and over again: you check if every number in the range 2 to 1,000,000 is prime, then you check if every number in the range 2 to 1,000,001 is prime, then you check if every number in the range 2 to 1,000,002 is prime, then you check ...

That's spectacularly wasteful.
Instead of doing that, work out all the primes in the range once, and store them. Then print them all.

Me? I'd be tempted to permanently store them: write the primes to a file, and read it back when you load your app - if the range is inside the file range, then you need do no more work, just print. If it isn't, then generate the new primes, and add them to the file for next time. After a few runs, your app probably doesn't need to calculate any primes for most checks...

You should set a flag at the beginning of your inner loop to indicate that the number is a prime. Then just before your break statement set it to false to indicate that it is not prime. You can then print the number after the loop completes, if the flag is still set to true.

Quote:

my problem it is
this programm not performance

No, your problem is that this program is wrong and don't print anything!
If your real program print correct result, you made a mistake while copying it here.

Quote:

this programm not performance

It mean that you want your program as fast as possible, it is optimization. This imply that you understand what your program and the reason it do it.
The first step is to read documentation about the problem integer factorization.

How do you know that you have to stop potential factors checking ?
you stop at num/2, what is the reason ?
When you check factors of 101 by hand, do you stop at 50 or do you stop earlier ?
If you stop at 50 because 51*2 is more than num, you have to take advantage that you already know that 2 is already checked and is not a factor of 101, neither 3 ...
When you have understood this and made necessary changes, performance will be better, but still far from optimum.

It is also a good idea to make a function isprime to separate concerns.

这篇关于如何在两个数字之间编写查找素数的代码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！