Программа для поиска простых чисел

Question

Я хочу найти простое число между 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();
        }
    }
}

Может ли кто-нибудь помочь мне и найти возможную ошибку в программе?

Answer 1

так что это в основном просто два опечатки , один из них - самый неудачный, for (int j = 2; j <= num; j++), что является причиной непродуктивного тестирования 1%2,1%3 ... 1%(10^15-1), которое продолжается очень долго, поэтому ОП "любой вывод" . Вместо этого должно было быть j < i;. Другое, второстепенное по сравнению, то, что i должно начинаться с 2, а не с 0:

for( i=2; i <= num; i++ )
{
    for( j=2; j < i; j++ ) // j <= sqrt(i) is really enough
....

Конечно, нельзя ожидать, что распечатка консоли из 28 триллионов простых чисел или около того будет завершена в любой разумный срок. Таким образом, первоначальная цель этой проблемы, очевидно, заключалась в том, чтобы распечатать непрерывный поток простых чисел до бесконечности . Следовательно, все решения, предлагающие простое использование сита Эратосфена, здесь совершенно бесполезны, поскольку простое сито Эратосфена ограничено - предел должен быть установлен заранее.

Что может сработать здесь, так это оптимизированное пробное деление, которое сохранит простые числа при их обнаружении и будет проверять не простые числа, а только все числа ниже кандидата.

Вторая альтернатива, с гораздо большей сложностью (то есть намного быстрее), состоит в использовании сегментированного сита из Эратосфена . Который является инкрементным и неограниченным.

Обе эти схемы будут использовать двухэтапное производство простых чисел : один будет производить и сохранять простые числа, которые будут использоваться на другом этапе тестирования (или просеивания), намного выше предела первого этап (конечно, ниже его квадрата - автоматически расширяется первый этап, так как второй этап будет идти все дальше и дальше вверх).

Answer 2

Форумы ExchangeCore в списке есть хорошее консольное приложение, которое пытается записать найденные простые числа в файл, похоже, вы также можете использовать этот же файл в качестве отправной точки, чтобы вам не пришлось перезапускать поиск простые числа из 2, и они обеспечивают загрузку этого файла со всеми найденными простыми числами до 100 миллионов, так что это было бы хорошим началом.

Алгоритм на странице также использует пару ярлыков (нечетные числа и проверяет только квадратный корень), что делает его чрезвычайно эффективным и позволяет вычислять длинные числа.

Answer 3

Честно говоря, некоторые из предложенных решений очень медленные, и, следовательно, являются плохими предложениями. Чтобы проверить простое число, вам нужен некоторый оператор деления / по модулю, но для вычисления диапазона вам не нужно.

По сути, вы просто исключаете числа, кратные ранее найденным простым числам, поскольку сами по определению не являются простыми числами.

Я не буду давать полную реализацию, так как это было бы легко, это подход в псевдокоде. (На моей машине фактическая реализация вычисляет все простые числа в Sytem.Int32 (2 миллиарда) в течение 8 секунд.

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 ГБ, а вычисление этого набора результатов занимает максимум 2 минуты.

Answer 4

Я знаю, что это тихий старый вопрос, но после прочтения здесь: Сито Эратосфена Wiki

Вот как я написал это из понимания алгоритма:

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 + " ");
}

В первом цикле мы заполняем массив логических значений значением true.

Второй цикл for начнется с 2, поскольку 1 не является простым числом, и проверит, не изменилось ли простое число, а затем присвоит false индекс j

последний цикл, который мы просто печатаем, когда он прост.

Answer 5

Вы также можете сделать это:

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;
    }
  }

Answer 6

Есть несколько очень оптимальных способов реализации алгоритма. Но если вы не очень разбираетесь в математике и просто используете определение простого числа как требование: число, которое делится только на 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 и далее до числа непосредственно перед собой. Это основные рассуждения.

Answer 7

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);}

        }
    }

}

Answer 8

Это решение отображает все простые числа от 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 + " "); }
        }

Answer 9

Это самый быстрый способ вычисления простых чисел в 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");
        }
    }

Answer 10

Очень похоже - из упражнения по внедрению Сита Эратосфена в 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;
    }
}