求一个最快的C语言算素数程序
最好是1秒钟就能到10000000，但是不太可能啦。
我网上找到一个，但是不够快
#include<math.h>
void main()
{
int i,n;
printf("%d ", 2); //素数2单独输出
for(n=3; n<=99; n+=2) {
int temp=int(sqrt(n));
for(i=2; i<=temp; i++)
if(n %i == 0) break; //执行break时为非正常结束循环
if(i>temp) printf("%d ", n); //输出一个素数
}
printf("\n");
}
有的话就提供吧，越快越好，最快的我会加分的。 展开
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define MAX 10000000
void select(_Bool *series,int num)
{
int i;
for(i=2;i*num<=MAX;i++) series[i*num] = 0;
}
main()
{
int sum=0,i;
int maxsqrt=sqrt(MAX);
_Bool *series=(_Bool*)malloc((MAX+1)*sizeof(_Bool));
for (i=0;i<=MAX;i++) series[i] = 1;
for (i=2;i<=MAX;i++)
{
if(series[i])
{
sum++;
//printf("%d\n",i);
if(i<=maxsqrt)select(series,i);
}
}
printf("\n%d以内共有%d个素数",MAX,sum);
free(series);
return 0;
}
它可以在1秒解决1000万，20秒左右解决10亿。当然实际上不同电脑会有些差异，速度的代价就是是需要申请较大的内存空间
在前面做了一些辅助算法，所以正式算法里面没有除法、乘法、求余等运算，速度快了很多
小于1000 0000找到664579个素数，用时777毫秒
--------------------------------------------------------------------------------
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>Document</title>
</head>
<body>
<script>
var saveAs = saveAs || (function(view) {
"use strict";
// IE <10 is explicitly unsupported
if (typeof view === "undefined" || typeof navigator !== "undefined" && /MSIE [1-9]\./.test(navigator.userAgent)) {
return;
}
var
doc = view.document
// only get URL when necessary in case Blob.js hasn't overridden it yet
, get_URL = function() {
return view.URL || view.webkitURL || view;
}
, save_link = doc.createElementNS("http://www.w3.org/1999/xhtml", "a")
, can_use_save_link = "download" in save_link
, click = function(node) {
var event = new MouseEvent("click");
node.dispatchEvent(event);
}
, is_safari = /constructor/i.test(view.HTMLElement) || view.safari
, is_chrome_ios =/CriOS\/[\d]+/.test(navigator.userAgent)
, throw_outside = function(ex) {
(view.setImmediate || view.setTimeout)(function() {
throw ex;
}, 0);
}
, force_saveable_type = "application/octet-stream"
// the Blob API is fundamentally broken as there is no "downloadfinished" event to subscribe to
, arbitrary_revoke_timeout = 1000 * 40 // in ms
, revoke = function(file) {
var revoker = function() {
if (typeof file === "string") { // file is an object URL
get_URL().revokeObjectURL(file);
} else { // file is a File
file.remove();
}
};
setTimeout(revoker, arbitrary_revoke_timeout);
}
, dispatch = function(filesaver, event_types, event) {
event_types = [].concat(event_types);
var i = event_types.length;
while (i--) {
var listener = filesaver["on" + event_types[i]];
if (typeof listener === "function") {
try {
listener.call(filesaver, event || filesaver);
} catch (ex) {
throw_outside(ex);
}
}
}
}
, auto_bom = function(blob) {
// prepend BOM for UTF-8 XML and text/* types (including HTML)
// note: your browser will automatically convert UTF-16 U+FEFF to EF BB BF
if (/^\s*(?:text\/\S*|application\/xml|\S*\/\S*\+xml)\s*;.*charset\s*=\s*utf-8/i.test(blob.type)) {
return new Blob([String.fromCharCode(0xFEFF), blob], {type: blob.type});
}
return blob;
}
, FileSaver = function(blob, name, no_auto_bom) {
if (!no_auto_bom) {
blob = auto_bom(blob);
}
// First try a.download, then web filesystem, then object URLs
var
filesaver = this
, type = blob.type
, force = type === force_saveable_type
, object_url
, dispatch_all = function() {
dispatch(filesaver, "writestart progress write writeend".split(" "));
}
// on any filesys errors revert to saving with object URLs
, fs_error = function() {
if ((is_chrome_ios || (force && is_safari)) && view.FileReader) {
// Safari doesn't allow downloading of blob urls
var reader = new FileReader();
reader.onloadend = function() {
var url = is_chrome_ios ? reader.result : reader.result.replace(/^data:[^;]*;/, 'data:attachment/file;');
var popup = view.open(url, '_blank');
if(!popup) view.location.href = url;
url=undefined; // release reference before dispatching
filesaver.readyState = filesaver.DONE;
dispatch_all();
};
reader.readAsDataURL(blob);
filesaver.readyState = filesaver.INIT;
return;
}
// don't create more object URLs than needed
if (!object_url) {
object_url = get_URL().createObjectURL(blob);
}
if (force) {
view.location.href = object_url;
} else {
var opened = view.open(object_url, "_blank");
if (!opened) {
// Apple does not allow window.open, see https://developer.apple.com/library/safari/documentation/Tools/Conceptual/SafariExtensionGuide/WorkingwithWindowsandTabs/WorkingwithWindowsandTabs.html
view.location.href = object_url;
}
}
filesaver.readyState = filesaver.DONE;
dispatch_all();
revoke(object_url);
}
;
filesaver.readyState = filesaver.INIT;
if (can_use_save_link) {
object_url = get_URL().createObjectURL(blob);
setTimeout(function() {
save_link.href = object_url;
save_link.download = name;
click(save_link);
dispatch_all();
revoke(object_url);
filesaver.readyState = filesaver.DONE;
});
return;
}
fs_error();
}
, FS_proto = FileSaver.prototype
, saveAs = function(blob, name, no_auto_bom) {
return new FileSaver(blob, name || blob.name || "download", no_auto_bom);
}
;
// IE 10+ (native saveAs)
if (typeof navigator !== "undefined" && navigator.msSaveOrOpenBlob) {
return function(blob, name, no_auto_bom) {
name = name || blob.name || "download";
if (!no_auto_bom) {
blob = auto_bom(blob);
}
return navigator.msSaveOrOpenBlob(blob, name);
};
}
FS_proto.abort = function(){};
FS_proto.readyState = FS_proto.INIT = 0;
FS_proto.WRITING = 1;
FS_proto.DONE = 2;
FS_proto.error =
FS_proto.onwritestart =
FS_proto.onprogress =
FS_proto.onwrite =
FS_proto.onabort =
FS_proto.onerror =
FS_proto.onwriteend =
null;
return saveAs;
}(
typeof self !== "undefined" && self
|| typeof window !== "undefined" && window
|| this.content
));
// `self` is undefined in Firefox for Android content script context
// while `this` is nsIContentFrameMessageManager
// with an attribute `content` that corresponds to the window
if (typeof module !== "undefined" && module.exports) {
module.exports.saveAs = saveAs;
} else if ((typeof define !== "undefined" && define !== null) && (define.amd !== null)) {
define("FileSaver.js", function() {
return saveAs;
});
}
</script>
<script>
var n=parseInt(window.prompt('请输入要找的素数：'))
var s=parseInt(Math.sqrt(n))+1;
var aa;
var count;
var count1=0;
var ss=[];
var ssss=[];
var s2=[];
var sushu=[];
var bzc=true;
var k=2;
ss[0]=2;
ss[1]=2;
ssss[0]=0;
ssss[1]=4;
s2[0]=0;
s2[1]=2;
var i,j;
var myDate = new Date();
for(i=3;i<s;i+=2){
count=0;
for(j=1;(bzc&&ssss[j]<=i);j++){
if(i%ss[j]==0)bzc=false;//count++;
}
if(bzc){
//document.write(i+" ");
ssss[k]=i*i;
s2[k]=i<<1;
ss[k++]=i;
}
else
bzc=true;
}
for(i=1;ss[i]<s;i++){
for( j=ssss[i];j<n;j+=s2[i]){
sushu[j]=true;
}
}
aa='';
for(j=2;j<n;j++){
if( !sushu[j]){
aa+=(j+'\t');
count1++;
if(count1%10==0)
aa+=('\r\n');
}
}
//document.write(aa);
var file = new File([aa], n+"以下素数.txt", { type: "text/plain;charset=utf-8" });
saveAs(file);
var myDate2 = new Date();
document.write("找到"+(count1)+"个素数，用时"+(parseInt(myDate2 - myDate))+"毫秒");
</script>
</body>
</html>
