判断质数以及求某数以内的质数

xml 代码

       今天去笔试，做了个关于求某数以内质数之和的题目，虽然做出来了，但是感觉效率还是很低，不过查了下，也没其他的效率高的方法（也许是baidu没用好的缘故）。先把自己的与大家一起分享，有什么建议希望大家不吝赐教。
#include<iostream.h>
#include <stdlib.h>
int main()
{
 //该程序可以用来判断一个数是否是质数，以及求出小于某个数范围之内的所有的质数

 int w;//保存要测试的数
 int q;//保存判断的值
 cout<<"请输入测试的数"<<endl;
 cin>>w;

 cout<<"是否判断，是就输入1，不是就任意输入"<<endl;
 cin>>q;
 int e=0;//保存质数的个数


 for(int i=2;i<w+1;i++) //被除数的遍历
 {
  if(q==1){//表明是用来判断的
   i=w;
  }
  int c=0; //保存整除因数的个数
  for(int j=2;j<w+1;j++)//除数遍历
  {

   if(i%j==0)//整除
   {
     c++;
   }
  }
  if(c==1)//表明只有一个整数因子
  {
   cout<<i<<"是质数"<<endl;
   e++;
  }
  if(q==1){
   if(c!=1)
   {
    cout<<i<<"不是质数"<<endl;
   }
   break;
  }
 }
 if(e>0)
  cout<<"共有"<<e<<"个质数"<<endl;
system("PAUSE");//系统函数，包含在<stdlib.h>头文件中，用于暂停屏幕
 return 0;
}

该程序在VC6.0环境下测试的能够正常运行。如果你提出那个2层循环用平方根代替以前的数能够提高效率，的确这样也可以，我好久没用C++了，所以平方的函数忘了，如果你想这样做也可以试下。

分享到：

因式分解的算法 | 动态添加和删除表单元素

• 2007-11-26 14:45
• 浏览 1976
• 评论(3)
• 论坛回复 / 浏览 (3 / 5689)
• 分类:编程语言
• 查看更多

评论

3 楼 stworthy 2008-01-26  

<p>来个Erlang版本的：</p><pre name='code' class='java'>-module(test).
-export([main/1]).

main(N) -&gt;
    L = calc(N, []),
    S = lists:foldl(fun(X, Total) -&gt; Total+X end, 0, L),
    io:format("质数：~p~n", [L]),
    io:format("总和：~p~n", [S]).
   
%统计某个数以内的所有质数
calc(1, L) -&gt; L;
calc(N, L) -&gt;
    case is_single(N) of
        false -&gt; calc(N-1, L);
        true -&gt; calc(N-1, [N|L])
    end.

%判断是否是质数
is_single(N) -&gt; is_single(N, N-1).
is_single(_N, 1) -&gt; true;
is_single(N, D) when N rem D ==0 -&gt; false;
is_single(N, D) -&gt; is_single(N, D-1).
</pre><p> </p>

2 楼 抛出异常的爱 2008-01-22  

package com.maodajun.javaeye5;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class SingleWord {
	List list = new ArrayList();
	/**
	 * 将list中的数据求合
	 * @return
	 */
	public int addAll(){
		int all = 0 ;
		String temp = null;
		for(Iterator it = list.iterator();it.hasNext();){
			temp = (String) it.next();
			all += Integer.parseInt(temp);
		}
		return all;
	}
	/**
	 * @deprecated
	 * 已过时方法
	 * 用于判断是否是质数
	 * @param str
	 */
	public void isSingle(String str){
		int tmp = Integer.parseInt(str);
		if(tmp<2){
			return;
		}
		for(int i = 2 ; Math.sqrt(tmp) >=i ; i ++ ){
			if(tmp%i==0){
				return;
			}
		}
		list.add(str);
	}
	/**
	 * 用来找到所有小于str的质数方法
	 * 
	 */
	public void findAllSingle(String str){
		int tmp = Integer.parseInt(str);
		for(int i = 0 ; tmp >i ;i ++){
			isOldSingle(""+i);
		}
	}
	/**
	 * 对输入的数值与已有的数值对比
	 * 看可否被整除.
	 * 
	 * @param str
	 */
	public void isOldSingle(String str){
		int tmp = Integer.parseInt(str);
		if(tmp<2){
			return;	
		}else{
			for(int i = 0 ; list.size()>i ;i++ ){
				int single =Integer.parseInt(list.get(i).toString());
				if(tmp%single ==0){
					return;
				}
			}			
		}
		list.add(str);
	}
	public List getList() {
		return list;
	}
	public void setList(List list) {
		this.list = list;
	}

}

package com.maodajun.javaeye5;

import java.util.ArrayList;
import java.util.List;

import junit.framework.TestCase;

public class SingleWordTest extends TestCase {

	public static void main(String[] args) {
		junit.textui.TestRunner.run(SingleWordTest.class);
	}

	public SingleWordTest(String arg0) {
		super(arg0);
	}

	protected void setUp() throws Exception {
		super.setUp();
	}

	protected void tearDown() throws Exception {
		super.tearDown();
	}

	/*
	 * Test method for 'com.maodajun.javaeye5.SingleWord.addAll()'
	 */
	public void testAddAll() {
		List list = new ArrayList();
		list.add("1");
		list.add("2");
		SingleWord singleword = new SingleWord();
		singleword.setList(list);
		int i = singleword.addAll();
		assertEquals(3,i);
	}
	public void testIsSingle(){
		SingleWord singleword = new SingleWord();
		singleword.isSingle("0");
		assertEquals(0,singleword.getList().size());
		singleword.isSingle("1");
		assertEquals(0,singleword.getList().size());
		singleword.isSingle("4");
		assertEquals(0,singleword.getList().size());
		singleword.isSingle("2");
		assertEquals(1,singleword.getList().size());
		singleword.isSingle("3");
		assertEquals(2,singleword.getList().size());
		singleword.isSingle("13");
		assertEquals(3,singleword.getList().size());
		singleword.isSingle("25");
		assertEquals(3,singleword.getList().size());
		
	}
	public void testIsOldSingle(){
		SingleWord singleword = new SingleWord();
		singleword.isOldSingle("0");
		assertEquals(0,singleword.getList().size());
		singleword.isOldSingle("1");
		assertEquals(0,singleword.getList().size());
		singleword.isOldSingle("2");
		assertEquals(1,singleword.getList().size());
		singleword.isOldSingle("3");
		assertEquals(2,singleword.getList().size());
		singleword.isOldSingle("4");
		assertEquals(2,singleword.getList().size());
		singleword.isOldSingle("5");
		assertEquals(3,singleword.getList().size());
		singleword.isOldSingle("6");
		assertEquals(3,singleword.getList().size());
		
	}
	public void testFindAllSingle(){
		SingleWord singleword = new SingleWord();
		singleword.findAllSingle("10");
		assertEquals(17,singleword.addAll());
		singleword .setList(new ArrayList());
		singleword.findAllSingle("20");
		assertEquals(77,singleword.addAll());

	}

}

1 楼 yzfy 2008-01-21  

请使用线性筛法