c# - 数が素数かどうかを調べる

Question

数値が素数かどうかを確認する正しい方法であるかどうかを尋ねたいと思いますか? 0 と 1 は素数ではないことを読んだからです。

int num1;

Console.WriteLine("Accept number:");
num1 = Convert.ToInt32(Console.ReadLine());
if (num1 == 0 || num1 == 1)
{
    Console.WriteLine(num1 + " is not prime number");
    Console.ReadLine();
}
else
{
    for (int a = 2; a <= num1 / 2; a++)
    {
        if (num1 % a == 0)
        {
            Console.WriteLine(num1 + " is not prime number");
            return;
        }

    }
    Console.WriteLine(num1 + " is a prime number");
    Console.ReadLine();
}

score 102 · Accepted Answer

var number;

Console.WriteLine("Accept number:");
number = Convert.ToInt32(Console.ReadLine());

if (IsPrime(number))
{
    Console.WriteLine("It is prime");
}
else
{
    Console.WriteLine("It is not prime");
}       

public static bool IsPrime(int number)
{
    if (number <= 1) return false;
    if (number == 2) return true;
    if (number % 2 == 0) return false;

    var boundary = (int)Math.Floor(Math.Sqrt(number));
          
    for (int i = 3; i <= boundary; i += 2)
        if (number % i == 0)
            return false;
    
    return true;        
}

I changed number / 2 to Math.Sqrt(number) because from in wikipedia, they said:

This routine consists of dividing n by each integer m that is greater than 1 and less than or equal to the square root of n. If the result of any of these divisions is an integer, then n is not a prime, otherwise it is a prime. Indeed, if n = a*b is composite (with a and b ≠</p>

then one of the factors a or b is necessarily at most square root of n

score 19 · Accepted Answer

Soner のルーチンを使用しますが、わずかなバリエーションがあります。単純なソリューションのトリックであるi等しいまで実行します。Math.Ceiling(Math.Sqrt(number))

boolean isPrime(int number)
{
    if (number == 1) return false;
    if (number == 2) return true;

    var limit = Math.Ceiling(Math.Sqrt(number)); //hoisting the loop limit

    for (int i = 2; i <= limit; ++i)  
       if (number % i == 0)  
           return false;
    return true;

}

score 12 · Accepted Answer

これを行う良い方法があります。

    static bool IsPrime(int n)
    {
        if (n > 1)
        {
            return Enumerable.Range(1, n).Where(x => n%x == 0)
                             .SequenceEqual(new[] {1, n});
        }

        return false;
    }

そして、あなたのプログラムを書く簡単な方法は次のようになります:

        for (;;)
        {
            Console.Write("Accept number: ");
            int n = int.Parse(Console.ReadLine());
            if (IsPrime(n))
            {
                Console.WriteLine("{0} is a prime number",n);
            }
            else
            {
                Console.WriteLine("{0} is not a prime number",n);
            }
        }

score 5 · Accepted Answer

Here's a good example. I'm dropping the code in here just in case the site goes down one day.

using System;

class Program
{
    static void Main()
    {
    //
    // Write prime numbers between 0 and 100.
    //
    Console.WriteLine("--- Primes between 0 and 100 ---");
    for (int i = 0; i < 100; i++)
    {
        bool prime = PrimeTool.IsPrime(i);
        if (prime)
        {
        Console.Write("Prime: ");
        Console.WriteLine(i);
        }
    }
    //
    // Write prime numbers between 10000 and 10100
    //
    Console.WriteLine("--- Primes between 10000 and 10100 ---");
    for (int i = 10000; i < 10100; i++)
    {
        if (PrimeTool.IsPrime(i))
        {
        Console.Write("Prime: ");
        Console.WriteLine(i);
        }
    }
    }
}

Here is the class that contains the IsPrime method:

using System;

public static class PrimeTool
{
    public static bool IsPrime(int candidate)
    {
    // Test whether the parameter is a prime number.
    if ((candidate & 1) == 0)
    {
        if (candidate == 2)
        {
        return true;
        }
        else
        {
        return false;
        }
    }
    // Note:
    // ... This version was changed to test the square.
    // ... Original version tested against the square root.
    // ... Also we exclude 1 at the end.
    for (int i = 3; (i * i) <= candidate; i += 2)
    {
        if ((candidate % i) == 0)
        {
        return false;
        }
    }
    return candidate != 1;
    }
}

score 2 · Accepted Answer

このバージョンは、素数の平方根のリストを計算し、素数のリストが平方根より下にあるかどうかのみをチェックし、リスト内の二分探索を使用して既知の素数を見つけます。ループして最初の 1,000,000 個の素数を確認したところ、約 7 秒かかりました。

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

namespace ConsoleApplication5
{
    class Program
    {
        static void Main(string[] args)
        {
            //test();
            testMax();
            Console.ReadLine();
        }

        static void testMax()
        {
            List<int> CheckPrimes = Enumerable.Range(2, 1000000).ToList();
            PrimeChecker pc = new PrimeChecker(1000000);
            foreach (int i in CheckPrimes)
            {
                if (pc.isPrime(i))
                {
                    Console.WriteLine(i);
                }
            }
        }
    }

    public class PrimeChecker{
        public List<int> KnownRootPrimesList;
        public int HighestKnownPrime = 3;

        public PrimeChecker(int Max=1000000){
            KnownRootPrimesList = new List<int>();
            KnownRootPrimesList.Add(2);
            KnownRootPrimesList.Add(3);
            isPrime(Max);
        }

        public bool isPrime(int value)
        {
            int srt = Convert.ToInt32(Math.Ceiling(Math.Sqrt(Convert.ToDouble(value))));
            if(srt > HighestKnownPrime)
            {
                for(int i = HighestKnownPrime + 1; i <= srt; i++)
                {
                    if (i > HighestKnownPrime)
                    {
                        if(isPrimeCalculation(i))
                        {
                                KnownRootPrimesList.Add(i);
                                HighestKnownPrime = i;
                        }
                    }
                }
            }
            bool isValuePrime = isPrimeCalculation(value);
            return(isValuePrime);
        }

        private bool isPrimeCalculation(int value)
        {
            if (value < HighestKnownPrime)
            {
                if (KnownRootPrimesList.BinarySearch(value) > -1)
                {
                    return (true);
                }
                else
                {
                    return (false);
                }
            }
            int srt = Convert.ToInt32(Math.Ceiling(Math.Sqrt(Convert.ToDouble(value))));
            bool isPrime = true;
            List<int> CheckList = KnownRootPrimesList.ToList();
            if (HighestKnownPrime + 1 < srt)
            {
                CheckList.AddRange(Enumerable.Range(HighestKnownPrime + 1, srt));
            }
            foreach(int i in CheckList)
            {
                isPrime = ((value % i) != 0);
                if(!isPrime)
                {
                    break;
                }
            }
            return (isPrime);
        }

        public bool isPrimeStandard(int value)
        {
            int srt = Convert.ToInt32(Math.Ceiling(Math.Sqrt(Convert.ToDouble(value))));
            bool isPrime = true;
            List<int> CheckList = Enumerable.Range(2, srt).ToList();
            foreach (int i in CheckList)
            {
                isPrime = ((value % i) != 0);
                if (!isPrime)
                {
                    break;
                }
            }
            return (isPrime);
        }
    }
}

score 1 · Accepted Answer

この例を 1 冊の本で見つけて、非常に洗練されたソリューションだと考えてください。

 static void Main(string[] args)
    {
        Console.Write("Enter a number: ");
        int theNum = int.Parse(Console.ReadLine());

        if (theNum < 3)  // special case check, less than 3
        {
            if (theNum == 2)
            {
                // The only positive number that is a prime
                Console.WriteLine("{0} is a prime!", theNum);
            }
            else
            {
                // All others, including 1 and all negative numbers, 
                // are not primes
                Console.WriteLine("{0} is not a prime", theNum);
            }
        }
        else
        {
            if (theNum % 2 == 0)
            {
                // Is the number even?  If yes it cannot be a prime
                Console.WriteLine("{0} is not a prime", theNum);
            }
            else
            {
                // If number is odd, it could be a prime
                int div;

                // This loop starts and 3 and does a modulo operation on all
                // numbers.  As soon as there is no remainder, the loop stops.
                // This can be true under only two circumstances:  The value of
                // div becomes equal to theNum, or theNum is divided evenly by 
                // another value.
                for (div = 3; theNum % div != 0; div += 2)
                    ;  // do nothing

                if (div == theNum)
                {
                    // if theNum and div are equal it must be a prime
                    Console.WriteLine("{0} is a prime!", theNum);
                }
                else
                {
                    // some other number divided evenly into theNum, and it is not
                    // itself, so it is not a prime
                    Console.WriteLine("{0} is not a prime", theNum);
                }
            }
        }

        Console.ReadLine();
    }

score 1 · Accepted Answer

ユーザーが指定した数まで素数の範囲を見つけることもできます。

コード：

class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Input a number to find Prime numbers\n");
            int inp = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("\n Prime Numbers are:\n------------------------------");
            int count = 0;

            for (int i = 1; i <= inp; i++)
            {
                for (int j = 2; j < i; j++) // j=2 because if we divide any number with 1 the remaider will always 0, so skip this step to minimize time duration.
                {
                    if (i % j != 0)
                    {
                        count += 1;
                    }
                }
                if (count == (i - 2))
                    {
                        Console.Write(i + "\t"); 
                    }

                count = 0;
            }

            Console.ReadKey();

        }
    }

score 1 · Accepted Answer

@Michealの回答に基づいていますが、負の数をチェックし、二乗を段階的に計算します

    public static bool IsPrime( int candidate ) {
        if ( candidate % 2 <= 0 ) {
            return candidate == 2;
        }
        int power2 = 9;
        for ( int divisor = 3; power2 <= candidate; divisor += 2 ) {
            if ( candidate % divisor == 0 )
                return false;
            power2 += divisor * 4 + 4;
        }
        return true;
    }

score 0 · Accepted Answer

関数のアルゴリズムは、n が 2 から sqrt (n) までの任意の整数の倍数であるかどうかをテストすることで構成されます。そうでない場合は True が返され、これは数値 (n) が素数であることを意味します。それ以外の場合は False が返されます。これは、n が 2 と sqrt(n) の最小整数部分の間の数値を除算することを意味します。

private static bool isPrime(int n)
        {
            int k = 2;
            while (k * k <= n)
            {
                if ((n % k) == 0)
                    return false;
                else k++;
            }
            return true;
        }

score 0 · Accepted Answer

アップデート

else if (value % 2 == 0)偶数を削除するために追加されました。avl_swedenに感謝

方法

拡張バージョン:

public static bool IsPrime(this int value)
{
    if (value < 2)
        return false;
    else if (value == 2)
        return true;
    else if (value % 2 == 0) /*updated*/
        return false;

    var root = Math.Sqrt(value);

    for (int i = 3; i <= root; i += 2)
    {
        if (value % i == 0)
            return false;
    }
    return true;
}

小切手

var primes = Enumerable.Range(1, 100).Where(x => x.IsPrime());
Console.WriteLine(string.Join(", ", primes));
/* Output
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
*/

使用法

12.IsPrime()    //false
13.IsPrime()    //true
151.IsPrime()   //true
2.IsPrime()     //true

score 0 · Accepted Answer

HackerRank チャレンジ (実行時間と複雑さ): 複数のテストケース、素数の場合。

入力形式: 最初の行には、テストケースの数である整数 T が含まれます。後続の T 行のそれぞれには、素数性をテストする整数 n が含まれています。

 int T = Convert.ToInt32(Console.ReadLine());
        int[] ar = new int[T];   

        for (int i = 0; i < ar.Length; ++i)
        {
            ar[i] = Convert.ToInt32(Console.ReadLine());
        }

        List<string> result = new List<string>();
        bool flag = true;
        for (int r = 0; r < ar.Length; ++r)
        {
            for (int i =2; i < (ar[r]>1000? ar[r]/4:ar[r]); ++i)
            {
                if (i != 1 && i != ar[r])
                {
                    if (ar[r] % i == 0)
                    {
                        flag = false;
                        break;
                    }
                }
            }

            if (flag && ar[r]!=1)
                result.Add("Prime");
            else
            {
                result.Add("Not prime");
                flag = true;
            }
              

        }

        foreach (var a in result)
        {
            Console.WriteLine(a);
        }

score 0 · Accepted Answer

関数のアルゴリズムは、n が 2 から sqrt (n) までの任意の整数の倍数であるかどうかをテストすることで構成されます。そうでない場合は True が返され、これは数値 (n) が素数であることを意味します。それ以外の場合は False が返されます。これは、n が 2 と sqrt(n) の最小整数部分との間の数値を除算することを意味します。

再帰バージョン

        // Always call it as isPrime(n,2)
        private static bool isPrime(int n, int k)
        {
            if (k * k <= n)
            {
                if ((n % k) == 0)
                    return false;
                else return isPrime(n, k + 1);
            }
            else
                return true;
        }

score -1 · Accepted Answer

1 つの行コードのみ:

    private static bool primeNumberTest(int i)
    {
        return i > 3 ? ( (Enumerable.Range(2, (i / 2) + 1).Where(x => (i % x == 0))).Count() > 0 ? false : true ) : i == 2 || i == 3 ? true : false;
    }

score -2 · Accepted Answer

これを試すこともできます：

bool isPrime(int number)
    {
        return (Enumerable.Range(1, number).Count(x => number % x == 0) == 2);
    }

score -2 · Accepted Answer

従来の方法を使用して素数を見つけるための最短の手法

    public string IsPrimeNumber(int Number)
    {
        int i = 2, j = Number / 2;
        for (; i <= j && Number % 2 != 0; i++);
        return (i - 1) == j ? "Prime Number" : "Not Prime Number";
    }

c# - 数が素数かどうかを調べる

30 に答える 30

Related

Reference