Prime number - Do you know another optimization for this algorithm?

Question

int n;
n=Convert.ToInt32(Console.ReadLine());
bool prime = true;
for(int i=2;i<n/2;i++)
{
if(n%i==0)
{
prime=false;
break;
}
}
if(prime==true)
{
Console.WriteLine("{0} is prime.",n);
}
else
{
Console.WriteLine("Not prime!");
}

Answer 1

That was more like pseudo code, even if it's almost JS valid code ;) (just replace 'and' by '&&', but first was better readable in this context)

Anyway, you could improve efficiency by storing square root before iteration (avoid performing n*n at each iteration):

prime = true;
if ( n != 2 and n & 1 == 0 ) {
prime = false;
}
else {
N = Math.sqrt(n);
for ( i = 3; i <= N; i += 2) {
if ( n % i == 0 ) {
prime = false;
break;
}
}
}

Answer 2

This is really good implementation... 👍 😃

Answer 3

@visph computing i*i efficient than computing sqrt(n)

here is the link

https://stackoverflow.com/questions/27112162/why-is-multiplied-many-times-faster-than-taking-the-square-root

Answer 4

It's good to be honest with people who can appreciate that, and can take truth in face. Sometimes I had problems with honesty, and saying directly what I want to say and I think it's correctly. Some people just can't take it. I preffer qualitty persons.

Answer 5

//try this
/*
To check a prime no : the number should not be divisible in the range of sqrt(number)
*/
int n=4;
n=Convert.ToInt32(Console.ReadLine());
bool prime = true;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
prime=false;
break;
}
}
if(prime==true)
{
Console.WriteLine("{0} is prime.",n);
}
else
{
Console.WriteLine("Not prime!");
}

Answer 6

In addition to limit test to numbers less or equal to square root of the range up limit (sqrt(n)), you could step by 2 to only test odd numbers appart two (if not divisible by 2, necessarly not divisable by all even numbers), and use of binary and instead of modulo for testing divibility by two:

prime = true;
if ( n != 2 and n & 1 == 0 ) {
prime = false;
}
else for ( i = 3; i*i <= n; i += 2) {
if ( n % i == 0 ) {
prime = false;
break;
}
}

(don't practice/use C#, so maybe above code is not C# valid ^^)

Answer 7

There's no optimization in your last code: you just check if 'prime' is true in the 'for' statement condition, but that's useless, as you already have exited the loop when 'prime' becomes false (with the 'break' keyword, in the if 'n%i == 0' statement). Anyway, even if you remove the now useless 'break' that would be stricly equivalent (just have to perform one more test before exiting the loop, and one more at each iteration ^^).

And obviously, it would be better optimized to compute the bound value (n/2, or better sqrt(n)) outside of the loop, rather than inside (the 'for' condition is inside the loop: performed before each iteration)...

Answer 8

Yes, you're rigth I've made some careless mistakes by swapping i and n at both conditions (but remember that I had wrote this code without testing it, as I don't really have experience with C#, focusing only on logic)...

It must be fixed by not just replacing i%n by n%i, but also changing the first 'if' statement condition from i&1 to n&1 and replace prime=true by prime=false ^^
(I will edit my previous posts to fix that ^^)

Anyway, I think finally that it was a good exercise for you as test and debug ;)

Answer 9

Also, trying to help writing code in a non well known language is a good exercise to focus on logic of programming ;)

Answer 10

And to say the truth, sqrt(n) as bound was an improvement I've already advices at sololearn many times (that the first time I see someone else give the same advice here), but focusing on logic have inspired me the step by 2 for the first time :)

Answer 11

Practice is essential for improving any language skills: I've done all the courses here a year ago, but I've forgot those I didn't practice ^^
On the other hand, that's not a good idea to practice too much languages as same time, before having mastered some of them: my first language skill is JS (and Html/Css, but they aren't programming languages), which I have good mastered even if I continue to learn and discover it... my next was Php, but now I've switched to Python on wich I focus, and unfortunatly, leave Java actually (but it will probably be the next one, or at least Kotlin for targeting android development). I've done very few C++ practice in the past (and others as Turbo Pascal with wich I've made my first step in object oriented programming, or some assembly -- on old Z80 processor) but C++ is not my priority, even if I hope master it a day, even if it's not impossible that I go to C# before, as I'm interested about 3D creation/programming and it seems to be used a lot in major 3D frameworks...

(I don't know to be anything else than honest, and I've always think that we should be honest first if we hope other people could be also)

Answer 12

Even if I'm convinced that "it's good to be honest", I love a meme of a french author André Gides who have wrote:
<< in a world where everyone cheats, it's the real man who is a charlatan >> (in book "Counterfeiters" -- 'Les faux-monayeurs" in french)
... because I've experienced that from long time: say the truth to somebody, he will search what you try to hide and doesn't believe what you say most of the time ^^

To be honest is difficult, because in your human actual world it's not well rewarded :(

Answer 13

@MR Programmer:

I'm agree, but only when you do them at each iteration: my way use a constant boundary computed before starting loop, not inside ;)

Answer 14

Why set and retrieve best answer mark on my answer, and even not let at least an upvote?!?

Answer 15

First, I want to try your code. thank you for your answer, I'm glad to see other way to think. by mistake I pressed best answer, but I think is the best. :)

Answer 16

The i & 1 perform binary logical and, to test if odd or even (logical and act as a bit mask pattern, so & 1 return only rightmost bit of a number: if one number is odd, else if zero number is even -- divisible by 2)

Answer 17

Now that you said, I had to figure it out for myself. Thank you for your explanations. I hope to talk with you about other algorithms.

Answer 18

And even, the first condition should be modified as: if (n != 2 and n % 1 == 0) ('and' or && : I don't what is used in C#)

Answer 19

( same for the binary and operator '&', I don't know if C# use this one -- but I think it's used in most of languages )

Answer 20

Yes, the first condition should test if n != 2 (else it's prime) and if n is even (else it could be prime) to avoid testing divisibility by each even number (so use a incremental step of 2)...