黑马程序员技术交流社区

标题: c#怎样求一个较大整数的最小质数因子 [打印本页]
作者: 百川    时间: 2014-3-17 23:16
标题: c#怎样求一个较大整数的最小质数因子
本帖最后由 百川 于 2014-3-18 11:58 编辑

如题。c#怎样求一个较大整数的最小质数因子。我试了一下用两个for循环，但是写的很乱
作者: 鬼鬼    时间: 2014-3-18 01:55
想了一会儿没想起来别的，只好写了个最简单的……
  1.         static int? getMinPrime(int num)
  2.         {
  3.             if (num < 2)
  4.                 return null;
  5.             for (int i = 2; i <= num; ++i)
  6.             {
  7.                 if (num % i == 0)
  8.                     return i;
  9.             }
  10.             return num;
  11.         }
复制代码
作者: zhl406893081    时间: 2014-3-18 02:34
本帖最后由 zhl406893081 于 2014-3-18 11:15 编辑

  2. <DIV class=blockcode>
  3. <BLOCKQUOTE>namespace ConsoleApplication1
  4. {

  6. class Program
  7. {
  8. static void Main(string[] args)
  9. {
  10. int number = Convert.ToInt32(Console.ReadLine());
  11. bool flag = true;
  12. if(number<2)
  13. Console.WriteLine("你输入的数字小于2");
  14. else if(质数(number))
  15. Console.WriteLine("你输入了一个质数,他的小质数因子是他本身");
  16. else if (number % 2 == 0)
  17. Console.WriteLine("你输入了一个偶数,他的最小质数因子为2");
  18. else
  19. {
  20. //质数中除了2没有其他偶数
  21. for (int i = 3; i < number; i+=2)
  22. {
  23. if (flag==质数(i)&&number%i==0)
  24. {
  25. Console.WriteLine("你输入的数字是{0},他的最小质数因子为{1}",number,i);
  26. break;
  27. }
  28. }
  29. }
  30. Console.ReadKey();
  31. }
  32. //判断n是否是质数
  33. static bool 质数(int n)
  34. {
  35. //是否是质数的标志
  36. bool flag = true;
  37. //对n开根号
  38. int s = (int)Math.Sqrt(n);
  39. //n除以每个比n开根号小比1大的自然数
  40. for (int i = 2; i <= s; i++)
  41. {
  42. //如果有能被整除的，则不是质数
  43. if (n % i == 0)
  44. {
  45. flag = false;
  46. return flag;
  47. }
  48. }
  49. return flag;
  50. }
  51. }
  52. }
复制代码


     
作者: cancle    时间: 2014-3-18 09:56
本帖最后由 cancle 于 2014-3-18 10:04 编辑

额，由于卤煮说的是一个较大整数的质数因子，我就没考虑数字是小于2的，我也用2个for循环来做的。（实际上这道题用1个for循环就够了，用2个就有点画蛇添足了）
  1. <font style="background-color: rgb(255, 255, 255);">private static int GetMin(int val)
  2.         {
  3.             int num = 0;
  4.             for (int i = 2; i < val; i++)//1不是质数，所以从2开始
  5.             {
  6.                 if (i == 2)//2是最小质数
  7.                 {
  8.                     if (val % i == 0)
  9.                     {
  10.                         num = i;
  11.                         break;
  12.                     }
  13.                     continue;
  14.                 }
  15.                 else
  16.                 {
  17.                     for (int j = 2; j < i; j++)
  18.                     {
  19.                         if (i % j == 0)//除尽了，说明不是质数
  20.                         {
  21.                             break;//跳出j的for循环，继续遍历i
  22.                         }
  23.                         else//除不尽,质数
  24.                         {
  25.                             if (val % i == 0)
  26.                             {
  27.                                 num = i;
  28.                                 break;
  29.                             }
  30.                         }
  31.                     }
  32.                     break;
  33.                 }
  34.             }
  35.             return num;
  36.         }</font>
复制代码
作者: 百川    时间: 2014-3-18 11:57
谢谢大家，结贴



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2