Program to find prime numbers

Question

I want to find the prime number between 0 and a long variable but I am not able to get any output   The program is   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  lt   num  i                                  for  int j   2  j  lt   num  j                                          if  i    j  amp  amp  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                        Can any one help me out and find what is the possible error in the program

User · Accepted Answer

You can do this faster using a nearly optimal trial division sieve in one  long  line like this   Enumerable Range 0  Math Floor 2 52 Math Sqrt num  Math Log num    Aggregate      Enumerable Range 2  num-1  ToList          result  index    gt             var bp   result index   var sqr   bp   bp          result RemoveAll i   gt  i  gt   sqr  amp  amp  i   bp    0            return result                The approximation formula for number of primes used here is p x   lt  1 26 x   ln x   We only need to test by primes not greater than x   sqrt num    Note that the sieve of Eratosthenes has much better run time complexity than trial division  should run much faster for bigger num values  when properly implemented

User · Answer

You can do also this   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  lt   3                  retVal   n  gt  1          else if  n   2    0    n   3    0                  retVal   false                 int i   5         while  i   i  lt   n                  if  n   i    0    n    i   2     0                      retVal   false                    i    6                 return retVal

User · Answer

Smells like more homework  My very very old graphing calculator had a is prime program like this  Technnically the inner devision checking loop only needs to run to i  1 2   Do you need to find  all  prime numbers between 0 and L   The other major problem is that your loop variables are  int  while your input data is  long   this will be causing an overflow making your loops fail to execute even once  Fix the loop variables

User · Answer

ExchangeCore Forums have a good console application listed that looks to write found primes to a file  it looks like you can also use that same file as a starting point so you don t have to restart finding primes from 2 and they provide a download of that file with all found primes up to 100 million so it would be a good start   The algorithm on the page also takes a couple shortcuts  odd numbers and only checks up to the square root  which makes it extremely efficient and it will allow you to calculate long numbers

User · Answer

Here is a solution with unit test   The solution   public class PrimeNumbersKata               public int CountPrimeNumbers int n                        if  n  lt  0  throw new ArgumentException  Not valide numbre                if  n    0    n    1  return 0              int cpt   0              for  int i   2  i  lt   n  i                                  if  IsPrimaire i   cpt                              return cpt                     private bool IsPrimaire int number                         for  int i   2  i  lt   number   2  i                                  if  number   i    0  return false                            return true                    The tests    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 lt ArgumentException gt      gt    primeNumbersKata CountPrimeNumbers -1                     Assert That ex Message     Not valide numbre                 Assert That ex Message  Is EqualTo  Not valide numbre

User · Answer

static void Main string   args         int i j          Console WriteLine  prime no between 1 to 100        for  i   2  i  lt   100  i                  int count   0          for  j   1  j  lt   i  j                           if  i   j    0                count count 1                       if   count  lt   2            Console WriteLine i                 Console ReadKey

User · Answer

You only need to check odd divisors up to the square root of the number   In other words your inner loop needs to start   for  int j   3  j  lt   Math Sqrt i   j  2            You can also break out of the function as soon as you find the number is not prime  you don t need to check any more divisors  I see you re already doing that     This will only work if num is bigger than two   No Sqrt  You can avoid the Sqrt altogether by keeping a running sum  For example   int square sum 1  for  int j 3  square sum lt i  square sum  4  j  -1           This is because the sum of numbers 1  3 5   7 9  will give you a sequence of odd squares  1 9 25 etc    And hence j represents the square root of square sum   As long as square sum is less than i then j is less than the square root

User · Answer

Very similar - from an exercise to implement Sieve of Eratosthenes in C    public class PrimeFinder       readonly List lt long gt   primes   new List lt long gt          public PrimeFinder long seed                CalcPrimes seed              public List lt long gt  Primes   get   return  primes           private void CalcPrimes long maxValue                for  int checkValue   3  checkValue  lt   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  amp  amp  prime  lt   Math Sqrt checkValue                                 isPrime   false                  break                                  return isPrime

User · Answer

Try this   void prime num long num            bool isPrime   true      for  long i   0  i  lt   num  i                  bool isPrime   true     Move initialization to here         for  long j   2  j  lt  i  j       you actually only need to check up to sqrt i                        if  i   j    0     you don t need the first condition                               isPrime   false                  break                                  if  isPrime                        Console WriteLine    Prime     i                         isPrime   true

User · Answer

To be quite frank  some of the suggested solutions are really slow  and therefore are bad suggestions  For testing a single number to be prime you need some dividing modulo operator  but for calculating a range you don t have to   Basically you just exclude numbers that are multiples of earlier found primes  as the are  by definition  not primes themselves   I will not give the full implementation  as that would be to easy  this is the approach in pseudo code   On my machine  the actual implementation calculates all primes in an Sytem Int32  2 bilion  within 8 seconds   public IEnumerable lt long gt  GetPrimes long max           we safe the result set in an array of bytes      var buffer   new byte long  gt  gt  4          1 is not a prime      buffer 0    1       var iMax    long Math Sqrt max        for long i   3  i  lt   iMax  i   2                    find the index in the buffer         var index   i  gt  gt  4             find the bit of the buffer          var bit    i  gt  gt  1   amp  7              A not set bit means  prime         if  buffer index   amp   1  lt  lt  bit      0                        var step   i  lt  lt  2              while step  lt  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            The solution requires a good understanding of bitwise operations  But it ways  and ways faster  You also can safe the result of the outcome on disc  if you need them for later use  The result of 17   10 9 numbers can be safed with 1 GB  and the calculation of that result set takes about 2 minutes max

User · Answer

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  lt  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

User · Answer

This solution displays all prime numbers between 0 and 100            int counter   0          for  int c   0  c  lt   100  c                          counter   0              for  int i   1  i  lt   c  i                                  if  c   i    0                    counter                                if  counter    2                Console Write c

User · Answer

in the university it was necessary to count prime numbers up to 10 000 did so  the teacher was a little surprised  but I passed the test  Lang c  void Main         int number 1      for long i 2 i lt 10000 i                  if PrimeTest i                         Console WriteLine number    quot   quot   i                      List lt long gt  KnownPrime   new List lt long gt     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

User · Answer

U can use the normal prime number concept must only two factors  one and itself   So do like this easy way  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  lt   num  i                                  int totalFactors   0                  for  int j   1  j  lt   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

User · Answer

An easier approach   what i did is check if a number have exactly two division factors which is the essence of prime numbers        List lt int gt  factorList   new List lt int gt         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  lt   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 lt int gt        reinitialize list

User · Answer

I know this is quiet old question  but after reading here  Sieve of Eratosthenes Wiki  This is the way i wrote it from understanding the algorithm   void SieveOfEratosthenes int n        bool   primes   new bool n   1        for  int i   0  i  lt  n  i            primes i    true       for  int i   2  i   i  lt   n  i            if  primes i               for  int j   i   2  j  lt   n  j    i                  primes j    false       for  int i   2  i  lt   n  i            if  primes i   Console Write i             In the first loop we fill the array of booleans with true    Second for loop will start from 2 since 1 is not a prime number and will check if prime number is still not changed and then assign false to the index of j   last loop we just printing when it is prime

User · Answer

This is the fastest way to calculate prime numbers in 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  lt   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

User · Answer

EDIT ADD   If Will Ness is correct that the question s purpose is just to output a continuous stream of primes for as long as the program is run  pressing Pause Break to pause and any key to start again  with no serious hope of every getting to that upper limit  then the code should be written with no upper limit argument and a range check of  true  for the first  i  for loop   On the other hand  if the question wanted to actually print the primes up to a limit  then the following code will do the job much more efficiently using Trial Division only for odd numbers  with the advantage that it doesn t use memory at all  it could also be converted to a continuous loop as per the above    static void primesttt ulong top number      Console WriteLine  Prime   2      for  var i   3UL  i  lt   top number  i    2        var isPrime   true      for  uint j   3u  lim    uint Math Sqrt  double i   j  lt   lim  j    2          if  i   j    0             isPrime   false          break                    if  isPrime  Console WriteLine  Prime    0     i           First  the question code produces no output because of that its loop variables are integers and the limit tested is a huge long integer  meaning that it is impossible for the loop to reach the limit producing an inner loop EDITED   whereby the variable  j  loops back around to negative numbers  when the  j  variable comes back around to -1  the tested number fails the prime test because all numbers are evenly divisible by -1  END EDIT   Even if this were corrected  the question code produces very slow output because it gets bound up doing 64-bit divisions of very large quantities of composite numbers  all the even numbers plus the odd composites  by the whole range of numbers up to that top number of ten raised to the sixteenth power for each prime that it can possibly produce   The above code works because it limits the computation to only the odd numbers and only does modulo divisions up to the square root of the current number being tested   This takes an hour or so to display the primes up to a billion  so one can imagine the amount of time it would take to show all the primes to ten thousand trillion  10 raised to the sixteenth power   especially as the calculation gets slower with increasing range   END EDIT ADD  Although the one liner  kind of  answer by  SLaks using Linq works  it isn t really the Sieve of Eratosthenes as it is just an unoptimised version of Trial Division  unoptimised in that it does not eliminate odd primes  doesn t start at the square of the found base prime  and doesn t stop culling for base primes larger than the square root of the top number to sieve   It is also quite slow due to the multiple nested enumeration operations   It is actually an abuse of the Linq Aggregate method and doesn t effectively use the first of the two Linq Range s generated   It can become an optimized Trial Division with less enumeration overhead as follows   static IEnumerable lt int gt  primes uint top number      var cullbf   Enumerable Range 2   int top number  ToList      for  int i   0  i  lt  cullbf Count  i          var bp   cullbf i   var sqr   bp   bp  if  sqr  gt  top number  break      cullbf RemoveAll c   gt  c  gt   sqr  amp  amp  c   bp    0       return cullbf      which runs many times faster than the SLaks answer   However  it is still slow and memory intensive due to the List generation and the multiple enumerations as well as the multiple divide  implied by the modulo  operations   The following true Sieve of Eratosthenes implementation runs about 30 times faster and takes much less memory as it only uses a one bit representation per number sieved and limits its enumeration to the final iterator sequence output  as well having the optimisations of only treating odd composites  and only culling from the squares of the base primes for base primes up to the square root of the maximum number  as follows   static IEnumerable lt uint gt  primes uint top number      if  top number  lt  2u  yield break    yield return 2u  if  top number  lt  3u  yield break    var BFLMT    top number - 3u    2u    var SQRTLMT     uint  Math Sqrt  double top number   - 3u    2u    var buf   new BitArray  int BFLMT   1 true     for  var i   0u  i  lt   BFLMT    i  if  buf  int i           var p   3u   i   i  if  i  lt   SQRTLMT            for  var j    p   p - 3u    2u  j  lt   BFLMT  j    p            buf  int j    false    yield return p        The above code calculates all the primes to ten million range in about 77 milliseconds on an Intel i7-2700K  3 5 GHz    Either of the two static methods can be called and tested with the using statements and with the static Main method as follows   using System  using System Collections  using System Collections Generic  using System Linq   static void Main string   args      Console WriteLine  This program generates prime sequences  r n       var n   10000000u     var elpsd   -DateTime Now Ticks     var count   0  var lastp   0u    foreach  var p in primes n     if  p  gt  n  break    count  lastp    uint p       elpsd    DateTime Now Ticks    Console WriteLine        0  primes found  lt    1   the last one is  2  in  3  milliseconds        count  n  lastp elpsd   10000      Console Write   r nPress any key to exit       Console ReadKey true     Console WriteLine        which will show the number of primes in the sequence up to the limit  the last prime found  and the time expended in enumerating that far   EDIT ADD   However  in order to produce an enumeration of the number of primes less than ten thousand trillion  ten to the sixteenth power  as the question asks  a segmented paged approach using multi-core processing is required but even with C   and the very highly optimized PrimeSieve  this would require something over 400 hours to just produce the number of primes found  and tens of times that long to enumerate all of them so over a year to do what the question asks   To do it using the un-optimized Trial Division algorithm attempted  it will take super eons and a very very long time even using an optimized Trial Division algorithm as in something like ten to the two millionth power years  that s two million zeros years       It isn t much wonder that his desktop machine just sat and stalled when he tried it      If he had tried a smaller range such as one million  he still would have found it takes in the range of seconds as implemented   The solutions I post here won t cut it either as even the last Sieve of Eratosthenes one will require about 640 Terabytes of memory for that range   That is why only a page segmented approach such as that of PrimeSieve can handle this sort of problem for the range as specified at all  and even that requires a very long time  as in weeks to years unless one has access to a super computer with hundreds of thousands of cores   END EDIT ADD

User · Answer

First step  write an extension method to find out if an input is prime  public static bool isPrime this int number          for  int i   2  i  lt  number  i               if  number   i    0                 return false                         return true         2 step  write the method that will print all prime numbers that are between 0 and the number input  public static void getAllPrimes int number        for  int i   0  i  lt  number  i                  if  i isPrime    Console WriteLine i

User · Answer

People have mentioned a couple of the building blocks toward doing this efficiently  but nobody s really put the pieces together  The sieve of Eratosthenes is a good start  but with it you ll run out of memory long before you reach the limit you ve set  That doesn t mean it s useless though -- when you re doing your loop  what you really care about are prime divisors  As such  you can start by using the sieve to create a base of prime divisors  then use those in the loop to test numbers for primacy   When you write the loop  however  you really do NOT want to us sqrt i  in the loop condition as a couple of answers have suggested  You and I know that the sqrt is a  pure  function that always gives the same answer if given the same input parameter  Unfortunately  the compiler does NOT know that  so if use something like   lt  Math sqrt x   in the loop condition  it ll re-compute the sqrt of the number every iteration of the loop    You can avoid that a couple of different ways  You can either pre-compute the sqrt before the loop  and use the pre-computed value in the loop condition  or you can work in the other direction  and change i lt Math sqrt x  to i i lt x  Personally  I d pre-compute the square root though -- I think it s clearer and probably a bit faster--but that depends on the number of iterations of the loop  the i i means it s still doing a multiplication in the loop   With only a few iterations  i i will typically be faster  With enough iterations  the loss from i i every iteration outweighs the time for executing sqrt once outside the loop   That s probably adequate for the size of numbers you re dealing with -- a 15 digit limit means the square root is 7 or 8 digits  which fits in a pretty reasonable amount of memory  On the other hand  if you want to deal with numbers in this range a lot  you might want to look at some of the more sophisticated prime-checking algorithms  such as Pollard s or Brent s algorithms  These are more complex  to put it mildly  but a lot faster for large numbers   There are other algorithms for even bigger numbers  quadratic sieve  general number field sieve  but we won t get into them for the moment -- they re a lot more complex  and really only useful for dealing with really big numbers  the GNFS starts to be useful in the 100  digit range

User · Answer

It may just be my opinion  but there s another serious error in your program  setting aside the given  prime number  question  which has been thoroughly answered    Like the rest of the responders  I m assuming this is homework  which indicates you want to become a developer  presumably    You need to learn to compartmentalize your code   It s not something you ll always need to do in a project  but it s good to know how to do it   Your method prime num long num  could stand a better  more descriptive name   And if it is supposed to find all prime numbers less than a given number  it should return them as a list   This makes it easier to seperate your display and your functionality   If it simply returned an IList containing prime numbers you could then display them in your main function  perhaps calling another outside function to pretty print them  or use them in further calculations down the line   So my best recommendation to you is to do something like this   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 lt long gt  primes   FindSmallerPrimes number        DisplayPrimes primes      public IList lt long gt  FindSmallerPrimes long largestNumber        List lt long gt  returnList   new List lt long gt           Find the primes  using a method as described by another answer  add them to returnList     return returnList     public void DisplayPrimes IList lt long gt  primes        foreach long l in primes                Console WriteLine    Prime     l ToString                Even if you end up working somewhere where speration like this isn t needed  it s good to know how to do it

User · Answer

One line code in C   -  Console WriteLine String Join Environment NewLine       Enumerable Range 2  300           Where n   gt  Enumerable Range 2   int Math Sqrt n  - 1           All nn   gt  n   nn    0   ToArray

User · Answer

so this is basically just two typos  one  the most unfortunate  for  int j   2  j  lt   num  j    which is the reason for the unproductive testing of 1 2 1 3     1  10 15-1  which goes on for very long time so the OP didn t get  any output   It should ve been j  lt  i  instead  The other  minor one in comparison  is that i should start from 2  not from 0    for  i 2  i  lt   num  i           for  j 2  j  lt  i  j        j  lt   sqrt i  is really enough        Surely it can t be reasonably expected of a console print-out of 28 trillion primes or so to be completed in any reasonable time-frame  So  the original intent of the problem was obviously to print out a steady stream of primes  indefinitely  Hence all the solutions proposing simple use of sieve of Eratosthenes are totally without merit here  because simple sieve of Eratosthenes is bounded - a limit must be set in advance    What could work here is the optimized trial division which would save the primes as it finds them  and test against the primes  not just all numbers below the candidate    Second alternative  with much better complexity  i e  much faster  is to use a segmented sieve of Eratosthenes  Which is incremental and unbounded   Both these schemes would use double-staged production of primes  one would produce and save the primes  to be used by the other stage in testing  or sieving   much above the limit of the first stage  below its square of course - automatically extending the first stage  as the second stage would go further and further up

User · Answer

There are some very optimal ways to implement the algorithm  But if you don t know much about maths and you simply follow the definition of prime as the requirement  a number that is only divisible by 1 and by itself  and nothing else   here s a simple to understand code for positive numbers   public bool IsPrime int candidateNumber        int fromNumber   2      int toNumber   candidateNumber - 1       while fromNumber  lt   toNumber                bool isDivisible   candidateNumber   fromNumber    0          if  isDivisible                        return false                     fromNumber              return true      Since every number is divisible by 1 and by itself  we start checking from 2 onwards until the number immediately before itself  That s the basic reasoning

User · Answer

public static void Main                   Console WriteLine  enter the number            int i   int Parse Console ReadLine              for  int j   2  j  lt   i  j                          for  int k   2  k  lt   i  k                                  if  j    k                                        Console WriteLine   0 is prime   j                        break                                    else if  j   k    0                                        break                                                    Console ReadLine

User · Answer

The Sieve of Eratosthenes answer above is not quite correct   As written it will find all the primes between 1 and 1000000   To find all the primes between 1 and num use   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                               The seed of the Aggregate should be range 1 to num since this list will contain the final list of primes   The Enumerable Range 1  Convert ToInt32 Math Floor Math Sqrt num     is the number of times the seed is purged

User · Answer

Prime Helper very fast calculation  public static class PrimeHelper        public static IEnumerable lt Int32 gt  FindPrimes Int32 maxNumber                return  new PrimesInt32 maxNumber               public static IEnumerable lt Int32 gt  FindPrimes Int32 minNumber  Int32 maxNumber                return FindPrimes maxNumber  Where pn   gt  pn  gt   minNumber              public static bool IsPrime this Int64 number                if  number  lt  2              return false          else if  number  lt  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 lt Int32 gt        private Int32 limit      private BitArray numbers       public PrimesInt32 Int32 limit                if  limit  lt  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  lt  limit  i                if  numbers i                   for  Int32 j   i   2  j  lt  limit  j    i                       numbers j    false             public IEnumerator lt Int32 gt  GetEnumerator                 for  Int32 i   2  i  lt  3  i                if  numbers i                   yield return i          if  limit  gt  2              for  Int32 i   3  i  lt  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  gt  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

[c#] Program to find prime numbers

Examples related to c#

Examples related to .net

Examples related to primes

Examples related to sieve-of-eratosthenes