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

Это может быть только мое мнение, но в вашей программе есть еще одна серьезная ошибка (не говоря уже о заданном вопросе о «простых числах», на который был дан исчерпывающий ответ).

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

Вам нужно научиться разделять свой код на части. Это не то, что вам всегда нужно делать в проекте, но хорошо знать, как это делать.

Ваш метод prime_num (long 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() );
    }
}

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

Пахнет домашней работой. В моем очень-очень старом графическом калькуляторе была такая простая программа. Технически цикл проверки внутреннего устройства должен выполняться только до i ^ (1/2). Вам нужно найти «все» простые числа от 0 до L? Другая серьезная проблема заключается в том, что ваши переменные цикла имеют значение «int», в то время как ваши входные данные - «длинные», это вызовет переполнение, из-за которого ваши циклы не выполнятся ни разу. Исправьте переменные цикла.

Однострочный код на 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()));                                    

Приведенный выше ответ Сито Эратосфена не совсем правильный. Как написано, он найдет все простые числа от 1 до 1000000. Чтобы найти все простые числа от 1 до num, используйте:

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

Начальное значение Aggregate должно находиться в диапазоне от 1 до num, поскольку этот список будет содержать окончательный список простых чисел. Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num)))) - это количество раз, когда семя очищается.

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

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

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

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

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

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

Вторая альтернатива, более сложная (т.е. намного более быстрая), - это использование сегментированного сита Эратосфена . Это происходит постепенно и неограниченно.

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

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

Я не буду приводить полную реализацию, поскольку это было бы несложно, это подход в псевдокоде. (На моей машине фактическая реализация вычисляет все простые числа в 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 минуты.

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

Я написал это так, исходя из понимания алгоритма:

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.

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

Очень похоже - из упражнения по реализации Решета Эратосфена на 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;
    }
}

Prime Helper очень быстрый расчет

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

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

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

Я сделал более простой подход: я проверил, имеет ли число ровно два коэффициента деления, что является сутью простых чисел.

    List<int> factorList = new List<int>();
    int[] numArray = new int[] { 1, 0, 6, 9, 7, 5, 3, 6, 0, 8, 1 };

    foreach (int item in numArray)
    {

        for (int x = 1; x <= item; x++)
        {
          //check for the remainder after dividing for each number less that number
            if (item % x == 0)
            {
                factorList.Add(x);
            }
        }
        if (factorList.Count == 2) // has only 2 division factors ; prime number
        {
            Console.WriteLine(item + " is a prime number ");
        }
        else
        {Console.WriteLine(item + " is not a prime number ");}

        factorList = new List<int>(); // reinitialize list
    }

Вот решение с модульным тестом:

Решение:

public class PrimeNumbersKata
    {
        public int CountPrimeNumbers(int n)
        {
            if (n < 0) throw new ArgumentException("Not valide numbre");
            if (n == 0 || n == 1) return 0;
            int cpt = 0;
            for (int i = 2; i <= n; i++)
            {
                if (IsPrimaire(i)) cpt++;
            }
            return cpt;
        }

        private bool IsPrimaire(int number)
        {

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

Тесты:

[TestFixture]
    class PrimeNumbersKataTest
    {
        private PrimeNumbersKata primeNumbersKata;
        [SetUp]
        public void Init()
        {
            primeNumbersKata = new PrimeNumbersKata();
        }
        [TestCase(1,0)]
        [TestCase(0,0)]
        [TestCase(2,1)]
        [TestCase(3,2)]
        [TestCase(5,3)]
        [TestCase(7,4)]
        [TestCase(9,4)]
        [TestCase(11,5)]
        [TestCase(13,6)]
        public void CountPrimeNumbers_N_AsArgument_returnCountPrimes(int n, int expected)
        {
            //arrange
            //act
            var actual = primeNumbersKata.CountPrimeNumbers(n);
            //assert
            Assert.AreEqual(expected,actual);
        }

        [Test]
        public void CountPrimairs_N_IsNegative_RaiseAnException()
        {
            var ex = Assert.Throws<ArgumentException>(()=> { primeNumbersKata.CountPrimeNumbers(-1); });
            //Assert.That(ex.Message == "Not valide numbre");
             Assert.That(ex.Message, Is.EqualTo("Not valide numbre"));

        }
    }

в вузе надо было считать простые числа до 10 000 сделали так, преподаватель немного удивился, но тест я сдал. Lang c #

void Main()
{
    int number=1;
    for(long i=2;i<10000;i++)
    {
        if(PrimeTest(i))
        {
            Console.WriteLine(number+++" " +i);
        }
    }
}

List<long> KnownPrime = new List<long>();
private bool PrimeTest(long i)
{
    if (i == 1) return false;
    if (i == 2)
    {
        KnownPrime.Add(i);
        return true;
    }
    foreach(int k in KnownPrime)
    {
        if(i%k==0)
            return false;
    }
    KnownPrime.Add(i);
    return true;
}