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

Question

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

Does this answer your question? [Program to find prime numbers](https://stackoverflow.com/questions/1510124/program-to-find-prime-numbers) and [Most elegant way to generate prime numbers](https://stackoverflow.com/questions/1042902/most-elegant-way-to-generate-prime-numbers) and [Generate Prime Numbers via Eratosthene's Sieve C#](https://stackoverflow.com/questions/41132850/generate-prime-numbers-via-eratosthenes-sieve-c-sharp) — , Aug 11 '21 at 11:12
Take a look at… [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) — JohnG, Aug 11 '21 at 11:14
This question has bien awnsered many, many, many times in mostly every existing languages. Do a search before opening a question. — 0x0000000000000, Aug 11 '21 at 11:20
Thanks all for the help, have resolved the issue. i know that it has been answered many many times. however just cant wrap my mind over . anyway have figured it out so thanks :D — Jay, Aug 11 '21 at 11:26

paxdiablo · Accepted Answer · 2021-08-12T12:05:55.150

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.

Oh My, Thanks for your help! it works now. Have figured it out after your help . — Jay, Aug 11 '21 at 11:22

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

1 Answers1