CODEWITHSUNDEEP
c#
Jay
Jay

Reputation: 21

C# Code to print out prime numbers from 5 to N

Prime Number Generator Code

Do know that this question should be quite basic but i have spent hours trying to figure out why my code is stuck in the loop as below. Have added a Console.WriteLine($"{counttemp} , {count1} "); in the if loop to check the 2 numbers and seems like it is not breaking out of the if condition when the condition is true

this is the console output for the writeline in the if loop
5 , 5
6 , 2
7 , 7
8 , 2
9 , 3
10 , 2
11 , 11
12 , 2
13 , 13
14 , 2
15 , 3
16 , 2
17 , 17
18 , 2
19 , 19

Problematic Loop??            
                for (count1 = 2; count1 <= counttemp  ; ++count1)
                {
                   
                    if(counttemp % count1 == 0)
                    {
                        Console.WriteLine($"{counttemp} , {count1} ");
                        Console.ReadKey();
                        primetest1 = 0;
                        break;
                    }
                }

full code sequence

static void Main(string[] args)
        {
            int prime1 = 10000, count1, primetest1, counttemp;

            for (counttemp = 5; counttemp <= prime1; counttemp++)
            {
                primetest1 = 1;
                for (count1 = 2; count1 <= counttemp  ; ++count1)
                {
                   
                    if(counttemp % count1 == 0)
                    {
                        Console.WriteLine($"{counttemp} , {count1} ");
                        Console.ReadKey();
                        primetest1 = 0;
                        break;
                    }
                }
                if (primetest1 == 1)
                {
                    Console.Write($"{counttemp}");
                }
            }
        }

Upvotes: 0

Views: 500

Answers (1)

paxdiablo
paxdiablo

Reputation: 882626

You're almost there. The problem is that you're checking if your candidate number is a prime by getting the remainder when divided by each number up to and including the number itself.

I think you'll find that N is a factor of N for all values of N. To fix this, you should only be checking up to but excluding the number.

And, as an aside, you don't really need to check all the way up to N - 1. You only need to go to the square root of N, adjusted up to the nearest integer. That's because, if it has a factor above the square root, you would already have found a factor below it.

Consider 24 as an example. It has 6, 8, and 12 as factors above the square root, but the matching values below the square root are 4, 3, and 2 respectively.

And there's a another trick you can use by realising that if a number is a multiple of a non-prime, it's also a multiple of every prime factor of that non-prime. In other words, every multiple of 12 is also a multiple of 2 and 3.

So you only need to check prime numbers up to the square root, to see if there's a factor. And prime numbers, other than two or three, are guaranteed to be of the form 6x-1 or 6x+1, so it's quite easy to filter out a large chunk of candidates very quickly, by checking only for those values.

In other words, check two and three as special cases. Then start at 5 and alternately add 2 and 4: 5, 7, 11, 13, 17, 19, .... Not every number in that set is prime (e.g, 25) every prime is guaranteed to be in that set.

You can check out an earlier answer of mine for more detail on why this is so, and how to do this sequence efficiently.

Upvotes: 1

Related Questions