检查素数

本文关键字：检查 | 更新日期: 2023-09-27 17:50:23

我的任务有问题。如果数字是否素数，我需要找到并提醒用户。

这是我的代码：

int a = Convert.ToInt32(number);
if (a % 2 !=0 )
{
    for (int i = 2; i <= a; i++)
    {
        if (a % i == 0)
        {
            Console.WriteLine("not prime");
        }
        else
        {
            Console.WriteLine("prime");
        }
        Console.WriteLine();
    }
}
else
{
    Console.WriteLine("not prime");
}
Console.ReadLine();

我哪里出了问题，我该如何解决？

检查素数

素数可以被1整除，并且它本身就需要检查这个数字是否正好有两个除数，从1开始直到数字，那么它就是素数。

 int devisors = 0;
 for (int i = 1; i <= a; i++)
     if (a % i == 0)                        
          devisors++;
 if (devisors == 2)                 
     Console.WriteLine("prime");
 else
     Console.WriteLine("not prime");

你可以跳过一次迭代，因为我们知道所有的整数都可以被1整除，那么素数就有一个正约数。由于1只有一个除数，我们需要跳过它，因为它不是素数。所以条件是，数字只有一个除数，而不是1，并且数字不应该是1，因为1不是素数。

 int devisors = 0;
 for (int i = 2; i <= a; i++)
     if (a % i == 0)                        
          devisors++;
 if (a != 1 && devisors == 1)                 
     Console.WriteLine("prime");
 else
     Console.WriteLine("not prime");

您只是打印素数或非素数，然后继续循环，而不是停止。实际上并不需要%2检查。适当修改：

int a = Convert.ToInt32(number);
bool prime = true;
if (i == 1) prime = false;
for (int i = 2; prime && i < a; i++)
    if (a % i == 0) prime = false;
if (prime) Console.WriteLine("prime");
else Console.WriteLine("not prime");
Console.ReadLine();

public bool isPrime(int num)
{
    for (int i = 2; i < num; i++)
        if (num % i == 0) 
            return false;                       
    return num == 1 ? false : true;
}

假设您的代码输出了大量消息，这些消息看起来杂乱无章，毫无意义？有3个关键问题：

  • 当你决定它不能成为主要时，你就不会突破你的for循环

  • 您假设它是素数，但可能不是，请参阅下面代码中的注释。

  • 你在比较a本身，它总是可以被a整除，<=在for条件中需要<

代码：

int a = Convert.ToInt32(number);
if (a % 2 != 0)
{
    for (int i = 3 i < a; i += 2) // we can skip all the even numbers (minor optimization)
    {
        if (a % i == 0)
        {
            Console.WriteLine("not prime");
            goto escape; // we want to break out of this loop
        }
        // we know it isn't divisible by i or any primes smaller than i, but that doesn't mean it isn't divisible by something else bigger than i, so keep looping 
    }
    // checked ALL numbers, must be Prime
    Console.WriteLine("prime");
}
else
{
    Console.WriteLine("not prime");
}
escape:
Console.ReadLine();

正如其他人所提到的，你们只能循环到a的平方根，通过计算平方根并替换这一行：

for (int i = 3 i < a; i += 2)

这个：

float sqrRoot = (Int)Math.Sqrt((float)a);
for (int i = 3 i <= sqrRoot; i += 2)

每次评估它很重要，否则你的程序会运行得更慢，而不是更快，因为每次迭代都会涉及一个平方根运算。

如果你不喜欢goto语句(我喜欢goto声明(，发布一条评论，我会用突破布尔值替换它(或者看看Dukeling最近的回答(。

我做了太多的素数检查。

我做到了：

bool isPrime = true;
        List<ulong> primes = new List<ulong>();
        ulong nCheck, nCounted;
        nCounted = 0;
        nCheck = 3;
        primes.Add(2);
        for (; ; )
        {
            isPrime = true;
            foreach (ulong nModulo in primes)
            {
                if (((nCheck / 2) + 1) <= nModulo)
                { break; }
                if (nCheck % nModulo == 0)
                { isPrime = false; }
            }
            if (isPrime == true)
            {
                Console.WriteLine("New prime found: " + (nCheck) + ", prime number " + (++nCounted) + ".");
                primes.Add(nCheck);
            }
            nCheck++;
            nCheck++;
        }

不过，这并不是你想要的，所以我会把它放在后台工作程序中，但把ulong列表作为并发列表，或者你可以在2个线程中访问的东西。或者在访问列表时锁定列表。如果素数hssn还没有计算出来，请等待。

另一种优化方法是使用埃拉托斯特内斯筛算法。

来自维基百科

通过Eratosthenes的方法找到所有小于或等于给定整数n的素数：
1.创建一个从2到n的连续整数列表：(2，3，4，…，n(
2.最初，让p等于2，即第一个素数
3.从p开始，以p为增量向上计数，并在列表中标记每个大于p本身的数字。这些将是p:2p、3p、4p等的倍数。；请注意，其中一些可能已经被标记
4.在未标记的列表中找到第一个大于p的数字。如果没有这样的数字，请停止。否则，让p现在等于这个数字(这是下一个素数(，并从步骤3开始重复。

When the algorithm terminates, all the numbers in the list that are not marked are prime.

C#代码

  int[] GetPrimes(int number) // input should be greater than 1
    {
        bool[] arr = new bool[number + 1];
        var listPrimes = new List<int>();
        for (int i = 2; i <= Math.Sqrt(number); i++)
        {
            if (!arr[i])
            {
                int squareI = i * i;
                for (int j = squareI; j <= number; j = j + i)
                {
                    arr[j] = true;
                }
            }
            for (int c = 1; c < number + 1; c++)
            {
                if (arr[c] == false)
                {
                    listPrimes.Add(c);
                }
            }
        }
        return listPrimes.ToArray();
    }

    private static void checkpirme(int x)
    {
        for (int i = 1; i <= x; i++)
        {
            if (i == 1 || x == i)
            {
                continue;
            }
            else
            {
                if (x % i == 0)
                {
                    Console.WriteLine(x + " is not prime number");
                    return;
                }

            }
        }
        Console.WriteLine(x + " is  prime number");
    }

其中x是用于检查是否为素数的数字

相关文章：