CareerCup

C ++ Version :

int n, m;

cout << "Please enter the #: " << endl;
cin >> n;

m = n +1;

for(int i = 2; i <= m/2; i++)
{
if(m%i == 0)
{
m = m + 1;
i=2;
}
}

cout << "M is: " << m << endl;

int n, n1, itr;
printf("\n\tEnter n: "); scanf("%d",&n);
n1=n+1;
while(1)
{
for(itr=2;itr<=n1/2;itr++)
if(n1%itr==0)break;
else continue;
if(n1/2<=itr)break;
else n1++;
}
printf("\n\n\tNext prime no is: [%d]",n1);

if(n1/2<=itr)break;
remove = from this condition otherwise if you enter 3 you will get next prime no 4

// Improvements to Illusions code/

// Consider only odd numbers after n.
int n, n1, itr;
printf("\n\tEnter n: "); scanf("%d",&n);

// take next odd number after n.

if(n%2==0) n1=n+1
else n1=n+2;

while(1)
{
for(itr=2;itr<=n1/2;itr++)
if(n1%itr==0)break;
else continue;
if(n1/2<=itr)break;
else n1=n1+2; // only consider odd numbers after n.
}
printf("\n\n\tNext prime no is: [%d]",n1);

there is an addition trick to use; instead of only dividing by odd number, you only need to divide by all of the prime numbers < n.

Instead of using n1/2 as the check condition, it is better to use squareroot(n1)

this link shows how it can be done right -
http://www.cs.mtu.edu/~shene/COURSES/cs201/NOTES/chap04/prime-2.html

thnaks jr

1. x=sprt(n)
2. check all prime numbers <= x (you do not have to go up to n/2)
if n can not be divided by any of these prime numbers, then it is also a prime

Ruby code:

def next_prime(number)
  next_number = number % 2 == 0 ? number+1 : number+2

  while true
    2.upto(next_number/2) do |i|
      next_number % i == 0 ? break : i
      return next_number if i >= next_number/2
    end
    
    next_number += 2
  end
end