在java中判断是否为素数的问题。

刘青山发布于 2010/11/10 17:31

阅读 2K+

答案 8

Java 素数

同样是搞Java，年薪15W和50W到底差在哪里？

这样判断素数打印出来的结果是：2-999，请问什么改代码才能出现正确的结果？谢谢！！

import java.util.regex.Matcher;
import java.util.regex.Pattern;


public class Test {
	public static void main(String[] args) {
		String str="^1?$|^(11+?)\1+$";
        Pattern pattern=Pattern.compile(str);
		
        for(int i=1;i<1000;i++){
			String tt=Integer.toBinaryString(i);
			Matcher matcher=pattern.matcher(tt);
			if(!matcher.matches()){
				System.out.println(Integer.parseInt(tt,2));
			}
		}
	}
}

加载中

红薯

2010/11/10 17:51

这段代码怎么会跟素数挂钩呢？

评论 (0) 引用此答案举报

华宰

2010/11/10 17:54

请看这里：http://www.oschina.net/code/snippet_4873_1464

评论 (0) 引用此答案举报

xiaowenliang

2010/11/10 18:34

1. 楼主你理解错了，这个正则之所以能判断是不是素数，最根本的一点是要把一个数换成相应的由1组成的串，而不是二进制串。

2->11 5->11111 ...etc.

2. 正则的back reference 请使用转义符 "^1?$|^(11+?)\\1+$"

评论 (0) 引用此答案举报

xiaowenliang

2010/11/10 18:35

引用来自#2楼“红薯”的帖子

这段代码怎么会跟素数挂钩呢？

这是对正则的一种很诡异的应用不过很有意思来判断一个数是不是包含除1以外的因子。

评论 (0) 引用此答案举报

nile

2010/11/10 21:58

        String str="^1?$|^(11+)\\1+$";  
        Pattern pattern=Pattern.compile(str);  
          
        StringBuffer sb = new StringBuffer();
        for(int i=1;i<1000;i++){
				sb.append("1");
			String tt = sb.toString();
            Matcher matcher=pattern.matcher(tt);  
            if(!matcher.matches()){  
                System.out.println(i);  
            }  
        }

不是转成二进制，而是连续写几个1
java中要把\1改成\\1

评论 (0) 引用此答案举报

nile

2010/11/10 21:58

结果基本靠普

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
211
223
227
229
233
239
241
251
257
263
269
271
277
281
283
293
307
311
313
317
331
337
347
349
353
359
367
373
379
383
389
397
401
409
419
421
431
433
439
443
449
457
461
463
467
479
487
491
499
503
509
521
523
541
547
557
563
569
571
577
587
593
599
601
607
613
617
619
631
641
643
647
653
659
661
673
677
683
691
701
709
719
727
733
739
743
751
757
761
769
773
787
797
809
811
821
823
827
829
839
853
857
859
863
877
881
883
887
907
911
919
929
937
941
947
953
967
971
977
983
991
997