Welcome to Chipset's homepage!

What is the next adjacent prime number?

// square root of a positive integer, also an positive integer
inline unsigned long sqrti(unsigned long n)
{
  unsigned long m = 0, r = 0;
  for(unsigned long i = 0; i < 16; ++i)
  {
    r <<= 1;
    m = (m << 2) + (n >> 30);
    n <<= 2;
    if(++r <= m)
    {
      m -= r;
      ++r;
    }
    else
      --r;
  }
    return r >> 1;
}

// what is the next adjacent prime number?
unsigned long next_prime(unsigned long n)
{
    if(n < 3)
      return 2;
    if(0 == (n & 1))
      ++n;
    while(true)
    {
      unsigned long m = sqrti(n) + 1;
      unsigned long i = 2;
      while(i < m)
      {
        if(0 == n % i)
          break;
            ++i;
      }
      if(i >= m)
        break;
        n += 2;
    }
    return n;
}

// a very simple test!
#include <iostream>
#include <cstdlib>
#include <ctime>

int main()
{
  const unsigned long SZ = 100;
  std::srand(std::time(0));
  for(unsigned i = 0; i < 100; ++i)
  {
    unsigned tmp = std::rand();
    std::cout << tmp << ", " << next_prime(tmp) << '\n';
  }
}

posted on 2010-12-24 15:50 Chipset 阅读(230) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理