unsigned char * PrintPrime( unsigned int nn )
{
const n = nn - (nn % 6 == 0 || nn % 6 == 5 ? (nn + 1) % 6 : nn % 6 - 1);
const MAX3=(n+2)/3;
unsigned char * tbl = malloc(MAX3);
unsigned int m=1,n1,n2, x;
memset(tbl,0,MAX3);
while (m < MAX3){
if(!TestBits(tbl, m) ){
x = m*(3*m+4)+1;
n2 = 6*m+4;
n1 = 2*m+1;
PutsInt(3*m+2);
while( x<MAX3){SetBit(tbl, x); if(x+n1>=MAX3) break; SetBit(tbl, x+n1); x += n2;}
} m++;
if(m >= MAX3) break;
if(!TestBits(tbl, m) ){
x = m*(3*m+2);
n2 = 6*m+2;
n1 = 4*m+1;
PutsInt(3*m+1);
while( x<MAX3){SetBit(tbl,x); if(x+n1>=MAX3) break; SetBit(tbl,x+n1);x+=n2;}
} m++;
}
return tbl;
}
int main(int argc, char *argv[]){
if(argc != 2) return 1;
PrintPrime(atoi(argv[1]));
return 0;
}
428を改造したコードだよ。君のと比べてみ。
君みたいな厨が現われないように859を書いたんだよ。
今となってはこのスレ、落とすのも埋めるのも変わらないかもね。
あ、桁溢れ忘れてた。
whileの条件の中は m < sqrt(MAX3/3) で、抜けたあとに
for(; m < MAX3; m++)
if(!TestBits(tbl, m))
PutsInt(m);
て感じで。
mallocの中はMAX3/7くらいで。
教えてくれ、悪意のないバカが日記を書き始めたらどうしたらいい。
君は頭なでなでして飴玉あげたいのかい? 俺にそんな母性本能はないよ。
そうなんないように早めに「最低428」ってハードルを作っといたんだよ。
そしたら平気でそのハードルくぐってきやがった(笑い)。
まあ、こういうのも含めて2ちゃんねるなわけだが。
もういいよ、止めないから埋めてくれ。
>>943 悪意の無い馬鹿が日記を書き始めたらどうしたらいいって?
放置すりゃいいんじゃね?
2年後に来る「悪意の無い馬鹿」を、止めたいんであれば、
そいつはその当時の熱気を知らないんだから、
「完全なコード」を乗せりゃいいんじゃね?
「そのコードに、自分が負けてるかどうかを簡単に検証できる」
用な環境を提示してやればいいんでは?
っていうか、428のコードは、何をどうするコードであって、
どうすれば「素数列挙」のコードになるの?
2年後にスレを観始めた人が、
そんな、細かいとこまでちゃんと、不完全な物も含めた全コードを、
main関数とかをちゃんとくっつけて、コンパイルして、検証すると思ってたの?
400MHzのプロセッサで50秒かかるコードを。
なんで、428のコードがあれば「悪意の無い馬鹿が日記を書き始める事は無い」
っておもったの?
>>940 にあるような、コードの訂正を、読んでる側の、「悪意の無い馬鹿」がやると思ってんの?
なんでさ、「完全なコード」を掲載しないの?
っていうか「428」のコードに、改造が必要だったのはなんで?
さらに、一億列挙するのに1.8秒のコードがあるのに
1億列挙するのに7秒かかるコードを「最低線」に選んだ理由はなに?
まあ、俺は939のコードに1億までの列挙で1200msecほど負けたので
もそっと精進しますが。
>>943 考え方はいろいろあるだろうけど、
やる気のある人間がやる気のない人間のスペースを奪うというのは
2ch的というより一般的な現象だね
君が向上しようとしていないから、どうすればいいかも分からないんだろうし、
泣いて哀れみ誘うしか止める手段がないんだろうね
1億1.8秒のコードはどうも怪しい気がするんですが俺だけですか。
unsigned char * PrintPrime( unsigned int nn ){
const n = nn - (nn % 6 == 0 || nn % 6 == 5 ? (nn + 1) % 6 : nn % 6 - 1);
const MAX3=n/3; unsigned char * tbl = malloc(MAX3/8); unsigned int m=1,n1,n2, x;
memset(tbl,0,MAX3/8);
while (m <= sqrt(MAX3/3)){
if(!TestBits(tbl, m) ){
x = m*(3*m+4)+1;
n2 = 6*m+4; n1 = 2*m+1;
PutsInt(3*m+2);
while( x<MAX3){SetBit(tbl, x); if(x+n1>=MAX3) break; SetBit(tbl, x+n1); x += n2;}
} m++;
if(!TestBits(tbl, m) ){
x = m*(3*m+2);
n2 = 6*m+2; n1 = 4*m+1;
PutsInt(3*m+1);
while( x<MAX3){SetBit(tbl,x); if(x+n1>=MAX3) break; SetBit(tbl,x+n1);x+=n2;}
} m++;
}
for(; m < MAX3; ){
if(!TestBits(tbl, m)){
PutsInt(3*m+2);
}m++;
if(m >= MAX3) break;
if(!TestBits(tbl, m)){
PutsInt(3*m+1);
}m++;
}
return tbl;
}
なんもやらなかった人間にくらべりゃどんなやつだってやる気あるだろ。
「〜と思ってました」
「自分が望んだのはこんなんじゃありません」
「私は暗にこういうことを伝えたかったんです」
「好きにすればいいです」
なんもせずにそういう言葉を平気で吐ける人間と
実際にがんばる人間だったらがんばる人間を応援したくなるよ。
無駄ながんばりなんだよな・・・
風邪引いて仕事してて
「あー私風邪でも仕事がんばってるなー」
なんて寝言ほざいてる馬鹿と一緒じゃん
迷惑なんだよ
と何度いいそうになったことか
自分中心で考えてて
周りのことを考えることができないんだろうなと思った。
>>952 風邪で仕事来ないでください。伝染ります。
で、
>>949 のコードを見てみたんだが、
「見つけた素数の倍数を、マークする(ふるう?)処理」って言うのは
√maxまででいいんだな。
そりゃそうか、
素数pをみつけたとき、pより小さい素数の倍数って言うのはすべてマークしてある。
つまり「pとp小さい素数の積」ってのはすべてマークしてある。
ってことはpの自乗よりも大きい数だけ、マークすればいい。
ってことは√maxよりも大きい素数を見つけた時は、
マークすべき数が無い、ってことか。
http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/47.txt % time ./furui8 100000000 > prime_list8
5.780u 0.500s 0:06.68 94.0% 0+0k 0+10io 0pf+0w
1億で6.68秒。7秒切った。
time ./furui8 1000000000 > prime_list8_2
68.970u 5.870s 1:22.28 90.9% 0+0k 0+46io 0pf+0w
10億だと83秒。すげ速くなった。
あとは「素数pを見つけたときに、pの自乗より大きい数だけマークする」ようにすればもっと速くなる。
この回答の為のヒント( つーか答え )は、
>>949のコードの
x=m*(3*m+4)+1 とか x=m*(3*m+2) にあるだろう。
これが漏れの中で飲み込めたら、実装しようと思う。
なにも調べないで他人のスペースを奪うやつが「やる気ある人」、「がんばる人間」。
煮詰まって発言が少なくなったやつは「やる気ない人」、「なんもやらなかった人間」。
やる気ないスレにやる気ある人が書き込んでんだから足引っぱるんじゃねえ。
過去ログ読めないやつのための859だった訳だがそういう問題じゃなかったと。
さて、
>>950のコードでも読もうか...
漏れの環境で
% time ./primes -p 100000000 > prime_list
9824 + 65536 = 75360
3.840u 0.630s 0:04.81 92.9% 0+0k 0+1io 0pf+0w
1億まで4.8秒?...漏れが学ぶべきポイントは多そうだ
planet risk見たいと思ったが。
radeon9000proで見れんかった。
グラボはみんな何で見てる?
demo起動->ゲフォ必要->電源落としてカード取り替え&ドライバ再インスコ->( ゚Д゚)ウマー
このくらいの気合があれば良いんだろうけど・・・・
グラフィックカードに素数列挙させるの?だったら凄そう。
SSE使えないかな
awe
少しコードを削ってみた。
http://kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/183.cpp % time ./furui13 100000000 > prime_list13
4.780u 0.600s 0:05.76 93.4% 0+0k 0+11io 0pf+0w
% time ./furui13 1000000000 > prime_list13_2
58.860u 5.530s 1:08.00 94.6% 0+0k 0+83io 0pf+0w
950並のループ展開が必要なんだろうか。
( すこしだけループ展開をしてみたりもしたんだが、むしろ遅くなったので、ループ展開に関しては、あんまり追求していない )
あるいは、2、3の倍数を除いた篩のとりあえずの極限に落ち着いてるんだろうか(ははっ、まさかね)。
2、3の倍数だけを抜いた方が、2、3、5を抜いた篩よりもコードが単純になる分最適化が効きやすかったりして有利かとも思ったが、
やはり859にあるように2,3,5を抜いた方が探索空間が小さい分だけ有利なんかなあ。
コードの単純さだと、950のは相当単純な反復に落としてあるし。
保守野鉄郎
965 :
デフォルトの名無しさん:2005/03/28(月) 22:23:35
これ、動かないよ?アクセスバイオレーションとか
primeベンチか、VC++6で作られてるから、
古すぎて動かないやつもいるのかもね
作者が古いのか、OSが新しすぎるのかw
967 :
デフォルトの名無しさん:皇紀2665/04/01(金) 08:36:10
MAC用もキボン
968 :
デフォルトの名無しさん:2005/05/09(月) 09:15:30
新たな参戦を求む
969 :
デフォルトの名無しさん:2005/05/09(月) 20:52:19
さいしょから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の倍数を抜いちゃったら?
971 :
デフォルトの名無しさん:2005/05/29(日) 15:20:17
, -=- -─‐-、
_ ´-─ ¬く  ̄  ̄ミ- 、
,,,,/ _==-ミァ-─‐-、 \''''''''''''ー--、,,,,,_
_,,,,-''"/ , ‐''" \ \、_,,,ー''ゞ" `ゞ、
-' " / / / | \ ヽ /"`
_,,-''''''"""''''' / / / / / || | i ヽ i /
´"''、. i / / / / / / || || |│ |ノス /
'、 |// / /___, -一ァ| /! |ト、|│ | | く」/
'、 |,-‐¬ ---┘'7 |! ハ! |,、-┼十|!/\/\
, -‐ ''" し' '´_ /,ィ二l |ト、/!ヽト、\_ヽ!|!l\:.. /
,r/ __ ,イ|リ ヾハ! ヽ! ,ィ⌒ヾミリノ/:::... \
/ ||ヽ -' / ̄ )` __ |ヒノ:} '` ,;\/\/
,r ' ヾ、 ,-、____ , イ ̄,r==- ==-' レ' /| |
/ ヽ `ーソ ' | |ト、,ヘ ′"" "" / / || |
. / \_ / | ハ ヽ`゙'ヘ ' ' / / | | | 1000GET
/ / / | ヽ 川\ 0 //! | | | |
/ / / 八 \川| |`ト- .. __ , イ‐ァヘ | | || |!
/ / / / \ \ 「`ー- 、 / .〉 ト、| ヽ、
,イ /-─=¬ニヘ、_ \ 厂\ 厂ヽ /!| | `ー=ヘ
-‐  ̄ /─ '  ̄ ├- ヽ\ \ノ\ \ 人 ハ!ヽ || |-┤ ヽ
/ /!‐-- | |\ ト、_`ヽ oヽ ト、! || |‐┤- ヽ
// 〉 __ / ├‐- || | 川-‐ | | 厂7! ハ! ├:┤  ̄ヽ
/ / ー ─  ̄ ├‐- リ || ハ!ヘ | | ト┤|/′ ヾ,┤ ゙i_
‐ ' 〉‐- | / /\ .|o | /ヽ/(′ ∨ \
972 :
デフォルトの名無しさん:2005/05/29(日) 17:24:58
2,3だと6のうち2つ
2.3.5だと30のうち8つ
2,3,5,7だと210のうち48
ΠpのうちのΠp-1
974get
975 :
デフォルトの名無しさん:2005/07/09(土) 09:03:08
2種類の分銅A,Bを使って、じゃがいも1gの物を量るために
成分A,Bを求める、またその正当性も求めるというアルゴリズムは
どのようにかけばいいのでしょうか?
知ってる方いましたらどうかおしえてください。
977 :
デフォルトの名無しさん:2005/07/09(土) 16:52:50
>>976 知らないならほっといてください。
知ってる方いましたら
どうかおしえてください。
拡張ユークリッドの互除法
979 :
デフォルトの名無しさん:2005/07/09(土) 23:51:05
拡張ユークリッドの互除法
は最大公約数を求めるものですよね?
それをどういうふうにつかえばよろしいのでしょうか?
自分勝手なやつだな。
ほっといたら迷惑なんだよ、お前は。
ここにいちゃいけない人間なんだってことを理解しろ。
981 :
デフォルトの名無しさん:2005/07/10(日) 01:23:14
>>980それは君
いくつものスレに迷惑文ばっか載せて
他人迷惑をかけている。
利用規約に反しているので
運営側に報告
IPアドレスから所在地をつかみ
損害賠償
オメ
テラキモス
983 :
:2005/07/10(日) 14:59:50
985 :
デフォルトの名無しさん:2005/07/11(月) 02:01:03
カコイイ!トオモテルノカナジブンデワ
987 :
デフォルトの名無しさん:
>>986あなたは利用規約に反しています。
再三の忠告にも関わらず
迷惑行為をしていますので
利用規約違反者として
あなたの通信記録より身元を判明させて頂き、
警察等に連絡させていただきます。