黑马程序员技术交流社区

标题: 如何判断是否为素数 [打印本页]
作者: xinchenglong    时间: 2013-8-26 14:21
标题: 如何判断是否为素数
昨天的时候，我做测试题，碰到一个判断是否为素数的题目，想了很长时间，但是不怎么好理解，求各位黑马人员各抒己见，有没有好的，更优的方式来解决这个问题呢？(遍历)
作者: 叶鹏    时间: 2013-8-26 16:31
  1.         void getSushu(){
  2.                
  3.                 for(int i=101;i<200;i++){
  4.            boolean b=false;
  5.                        
  6.                   double Num=0;
  7.                   if(i%2!=0){
  8.                           Num=Math.sqrt(i);
  9.                           for(int j=2;j<=Num;j++){
  10.                                   if(i%j==0){
  11.                                           b=false;
  12.                                           break;
  13.                                   }else{
  14.                                
  15.                                           b=true;
  16.                                                   }
  17.                                   }
  18.                           if(b==true){
  19.                                   System.out.println(i);
  20.                                   
  21.                                 }
  22.                           }
  23.                 }
复制代码
这是我做的一个1求从101到200之间的素数，求任意的素数只需要改变循环下表，你可以看下，希望对你有用
作者: 胡盼盼    时间: 2013-8-26 17:06

这两个网页你可以看看，希望能帮到你
http://www.cnblogs.com/CSharpSPF/archive/2012/04/04/2432105.html
http://www.cnblogs.com/luluping/archive/2010/03/03/1677552.html
作者: brucel50    时间: 2013-8-26 18:22
把我这笨拙的代码发来看看：
  1. using System;
  2. namespace Que
  3. {
  4.         class Program
  5.         {
  6.                 static void Main(string[] args)
  7.                 {
  8.                         string sInput = "";
  9.                         while(true)
  10.                         {
  11.                                 Console.WriteLine("请输入一个数，系统将判断此数是否为素数，若输入为quit，则退出程序");
  12.                                 sInput = Console.ReadLine();
  13.                                 if(sInput == "quit")
  14.                                 {
  15.                                         Console.WriteLine("程序即将退出...");
  16.                                         break;
  17.                                 }
  18.                                 //能运行到这里，说明用户没有输入"quit"，接下来判断是否是合法的
  19.                                 int iNum;
  20.                                 bool bifSuccess = int.TryParse(sInput,out iNum);
  21.                                 if(!bifSuccess)
  22.                                 {
  23.                                         Console.WriteLine("输入有误，程序将重新执行...");
  24.                                         continue;
  25.                                 }
  26.                                 //能运行到这里说明，可以判断这个数是否为素数了
  27.                                 //iNum是这个数，从iNum到1判断，iNum包含不包含除了1、它本身之外的约数
  28.                                 //1 1%[1,1]  2 2%[1,2] ...
  29.                                 bool biNumisSushu = true;                               
  30.                                 if(iNum != 1&&iNum != 2)
  31.                                 {
  32.                                         for(int i = iNum-1;i>=2;i--)
  33.                                         {
  34.                                                 if(iNum%i==0)
  35.                                                 {       
  36.                                                         if(i!=1&&i!=iNum)
  37.                                                         {
  38.                                                                 Console.WriteLine("这个数不是素数！");
  39.                                                                 biNumisSushu = false;
  40.                                                                 break;
  41.                                                         }
  42.                                                 }                                       
  43.                                         }
  44.                                 }                               
  45.                                 //运行到这里，说明这个数是素数
  46.                                 if(biNumisSushu)
  47.                                 {
  48.                                         Console.WriteLine("这个数是素数！");                                       
  49.                                 }       
  50.                         }                       
  51.                 }
  52.         }
  53. }
复制代码
作者: 天涯浪子    时间: 2013-8-26 19:53
static void Main(string[] args)
        {
        
              for(int i=2;i<=100;i++)
            {
                 if(IsNumberOK(i))
                  { //判断是素数时
                  Console.WriteLine(i);//这是判断成功的数
                   }
            }
              Console.ReadKey();
        }
         static bool IsNumberOK(int number)
                  {
                       //判断是否为素数
                        //规则是什么自己去写
                  }
作者: xinchenglong    时间: 2013-8-26 20:47
{:soso_e127:}你说的很有道理啊，还是没有解决根本问题啊！还是要谢谢你啊……
作者: xinchenglong    时间: 2013-8-26 20:47
楼上的帅哥美女们，多谢啦
作者: 小天    时间: 2013-8-27 12:25
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;

  6. namespace test7
  7. {
  8.     class Program
  9.     {
  10.         static void Main(string[] args)
  11.         {
  12.             //判断某个数是不是素数
  13.             int num = 7;
  14.             int count = 0;
  15.             for (int i = 1; i <= num; i++)
  16.             {
  17.                 if (num % i == 0)
  18.                 {
  19.                     count++;
  20.                 }
  21.             }
  22.             if (count > 2)
  23.             {
  24.                 Console.WriteLine("{0}不是素数",num);
  25.             }
  26.             else
  27.             {
  28.                 Console.WriteLine("{0}是素数",num);
  29.             }
  30.             Console.ReadKey();
  31.         }
  32.     }
  33. }
复制代码
作者: 赵祥    时间: 2013-8-28 01:18
最优算法，判断这个数是不是素数，只需循环到这个数的开平方根即可 ，比如求100是否素数，只需求到√100即可判断出来是否素数了
作者: 马晓凤    时间: 2013-8-28 08:50
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;

  6. namespace test7
  7. {
  8.     class Program
  9.     {
  10.         static void Main(string[] args)
  11.         {
  12.             //判断某个数是不是素数
  13.             int num = 1;//要判断的数   
  14.             bool isSuShu = true;
  15.             if (num!=1&&num!=0)//0和1既不是素数也不是合适
  16.             {
  17.                 for (int i = 2; i <= Math.Sqrt(num); i++)
  18.                 {
  19.                     if (num % i == 0)
  20.                     {
  21.                         isSuShu = false;
  22.                         break;
  23.                     }               
  24.                 }
  25.             }
  26.             else
  27.             {
  28.                 isSuShu = false;
  29.             }
  30.             if (true==isSuShu)
  31.             {
  32.                 Console.WriteLine(num+"：是素数");
  33.             }
  34.             else
  35.             {
  36.                 Console.WriteLine(num + "：不是素数");
  37.             }
  38.          
  39.            
  40.            
  41.             Console.ReadKey();
  42.         }
  43.     }
  44. }
复制代码
借用楼上的代码，我做一点小小的优化



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