Dirichlet's Theorem on Arithmetic Progression

poj3006 Dirichlet's Theorem on Arithmetic Progressions

Dirichlet's Theorem on Arithmetic ProgressionDirichlet's Theorem on Arithmetic Progression

很显然这是一题有关于素数的题目。

注意数据的范围,爆搜超时无误。

这里要用到筛选法求素数。

筛选法求素数的大概思路是:

如果a这个数是一个质数,则n*a不是质数。(年轻的孩子们不要纠结于判断a是否为素数)

用一个数组实现就是:

memset(prime,true,sizeof(prime));

if (prime[i]) prime[i*j]=false;

部分程序如下:

Dirichlet's Theorem on Arithmetic Progression
const max=1000005;
bool prime[1000005];
memset(prime,true,sizeof(prime));
for(i = 3 ; i <= ::max ; i ++ )
{
for(j = 3 ; j <= ::max/i ; j ++)
{
if(prime[i])
{
prime[i * j] = false;
}
}
}
Dirichlet's Theorem on Arithmetic Progression

之后将中间进行小小的优化:

我们知道偶数中,除了2,其他的都是合数。

所以就可以将i++ 和 j++改成i+=2,j+=2;

再将除2以外的偶数判为false;以及注意一下特殊的值: 1和0是false;(要记住,c++的数组是从0~max的,所以0要考虑在内)

优化后的程序如下:

Dirichlet's Theorem on Arithmetic Progression
const int max = 1000005;
bool prime[1000005]={false}; memset(prime,true,sizeof(prime));
for(i = 3 ; i <= 1000 ; i += 2 )
{
for(j = 3 ; j <= ::max / i ; j += 2)
{
if(prime[i])
{
prime[i * j] = false;
}
}
}
for(i = 4 ; i <= ::max; i += 2 )
{
prime[i] = false;
}
prime[1] = prime[0] = false;
Dirichlet's Theorem on Arithmetic Progression

这样,这题就可以在我们拟好的素数表中找到第n个要求的素数。用一个简单的循环就可以搞定。。hoho

附上我的程序:

Dirichlet's Theorem on Arithmetic Progression
#include<iostream>
#include<cstring>
using namespace std;
const int max = 1000005;
bool prime[1000005]={false};
int main()
{
int i,a,d,n,j;
memset(prime,true,sizeof(prime));
for(i = 3 ; i <= 1000 ; i += 2 )
{
for(j = 3 ; j <= ::max / i ; j += 2)
{
if(prime[i])
{
prime[i * j] = false;
}
}
}
for(i = 4 ; i <= ::max; i += 2 )
{
prime[i] = false;
}
prime[1] = prime[0] = false; while(cin >> a >> d >> n,a != 0 && d != 0 && n != 0)
{
j = 0;
for (i = a; j < n; i += d)
{
if (prime[i])
{
j++;
}
}
cout << i - d << endl;
}
return 0;
}
Dirichlet's Theorem on Arithmetic Progression

(最后的题外话,不懂怎么搞的老是忘记 memset的时候要用cstring...← ←...哎。。还是太年轻了)

随笔- 76  文章- 0  评论- 653 

html5 Web Workers

 

虽然在JavaScript中有setInterval和setTimeout函数使javaScript看起来好像使多线程执行,单实际上JavaScript使单线程的,一次只能做一件事情(关于JavaScript单线程可以看看setTimeout()和setInterval() 何时被调用执行),看个简单的例子证明一下

Dirichlet's Theorem on Arithmetic Progression
<!DOCTYPE html>
<html>
<head>
<title>Web Workers</title>
</head>
<body>
<h1>Web Workers</h1> <script type="text/javascript">
setTimeout(function(){
console.log('timeout function');
},1000);
alert('do not close');
</script>
</body>
</html>
Dirichlet's Theorem on Arithmetic Progression

页面一运行就会弹出一个对话框,如果setTimeout是在另外一个线程运行,那么过一秒钟控制台就会打印“timeout function”,事实是只要不关闭对话框,控制台永远不会输出文字,这两句话确实是在一个线程内运行的。

这样的设计使JavaScript比较简单,但有时候也很令人烦恼,因为单线程的设计意味着JavaScript代码必须很快运行完,常见的问题就是一段复杂的JavaScript脚本会中断页面其它脚本执行,甚至会出现页面失去响应,这也就是为什么ajax的API要设计成异步的。

Web Workers

在html5规范中引入了web workers概念,解决客户端JavaScript无法多线程的问题,其定义的worker是指代码的并行线程,不过web worker处于一个自包含的环境中,无法访问主线程的window对象和document对象,和主线程通信只能通过异步消息传递机制。(《JavaScript权威指南》)

web worker

我们需要把希望单独执行的javascript代码放到一个单独的js文件中,然后在页面中调用Worker构造函数来创建一个线程,参数是该文件路径,参数存放如果是相对地址,那么要以包含调用Worker构造函数语句所在脚本为参照,如果是绝对路径,需要保证同源(协议+主机+端口)。这个文件不需要我们在页面使用script标签显示引用

var worker=new Worker('js/worker.js');

这时候这个文件就会被异步加载并在后台执行,创建成功地worker是酱紫的

Dirichlet's Theorem on Arithmetic Progression

我们可以看到worker对象只有两个属性,其实是两个回调函数句柄

  1. onerror:当worker运行出现错误,并且没有在worker中ing捕获,会在此捕获
  2. onmessage:当worker向主线程发送消息是调用

在其prototype内有两个重要方法

  1. postMessage:很熟悉的赶脚,之前我们介绍过window对象的postMessage()方法,woker的postMessage方法和window的比较类似,但参数略有不同,只需要传递消息内容就可以,而且支持所有JavaScript原生数据类型,当然不放心的话同样也可以序列化为字符串传递
  2. terminate:终止worker执行,有些worker执行比较慢,主线程可以主动终止其执行

简单的小例子

在一个页面显示0~10000内所有可以被n整除的数,当然我们不用i*n这种,要略微使计算显得复杂一些嘛

index.html

Dirichlet's Theorem on Arithmetic Progression
 1 <!DOCTYPE html>
2 <html>
3 <head>
4 <title>Web Workers</title>
5 </head>
6 <body>
7 <h1>Web Workers</h1>
8
9 <div id="test" style="width:500px;"></div>
10 <script type="text/javascript">
11 var worker=new Worker('js/worker.js');
12 worker.postMessage({
13 n:69
14 });
15
16 worker.onmessage=function(e){
17 var test=document.getElementById('test').innerHTML=e.data;
18 };
19 </script>
20 </body>
21 </html>
Dirichlet's Theorem on Arithmetic Progression

/js/worker.js

Dirichlet's Theorem on Arithmetic Progression
function calc(n){
var result=[];
for(var i=1;i<10000;i++){
var tem=i;
if(i%n==0){
if(i%(10*n)==0){
tem+='<br/>';
}
result.push(tem);
}
} self.postMessage(result.join(' '));
self.close();
} onmessage=function(e){
calc(e.data.n);
};
Dirichlet's Theorem on Arithmetic Progression

Dirichlet's Theorem on Arithmetic Progression

好像有几点没提到

worker.onmessage

绑定主线程的message事件,当worker调用postMessage时方法时,绑定的事件处理程序会被调用到,传递来的数据可以使用MouseEvent的data属性获取,通过target属性还可以获取worker对象

Dirichlet's Theorem on Arithmetic Progression

self是什么

self是woker中对自身的引用,有些像this

close()

在worker内部调用close()方法效果和在外部调用worker实例的terminate()方法效果一样,终止worker运行

onmessage

在这个句柄内接收外部调用者传递的参数,参数可以通过e.data获取

self.postMessage()

没错通过这个方法我们可以在worker内把结果传递给主线程,主线程上绑定的message事件的处理程序会被调用

worker的作用域

web worker的简单用法就是这样,但有些姿势还是得了解一下。

全新的JavaScript环境

当一个Worker实例被创建的时候,它会在一个全新的JavaScript运行环境中,完全和创建worker的脚本分离开,即使我们传递的消息是引用类型它们也是复制传递的,修改worker中的参数不影响创建脚本中的参数。

importScripts()

我们可以通过importScripts()方法通过url在worker中加载库函数,

importScripts('utility/dialog.js','common/cookie.js');

方法可以接受多个url,相对地址的url以当前worker为参照,方法会按照参数顺序依次下载运行库函数,如果中间某个脚本出错,剩下的都不会被载入和执行,而且这个方法是同步的,只有所有脚本都加载、运行完后才会返回。

worker执行模型

worker线程从上到下同步运行它的代码,然后进入异步阶段来对事件及计时器响应,如果worker注册了message事件处理程序,只要其有可能触发,worker就一直在内存中,不会退出,但如果worker没有监听消息,那么当所有任务执行完毕(包括计数器)后,他就会退出。

web worker中可以使用什么

 前面提到在worker中不能使用window对象和docuemnt对象,那么能够使用什么呢

  • JavaScript的全局对象:JSON、Date()、Array
  • self自身引用
  • location对象,但是其属性都是只读的,改了也影响不到调用者
  • navigator对象
  • setTimeout()、setInterval()及其对应清除方法
  • addEventListener()、removeEventListener()

最后

web worker还支持sub worker和共享worker,这方面没有太仔细看,浏览器兼容性也不讨理想,有兴趣同学可以上网搜索研究一下。

 
 
分类: HTML5
 
分类: poj
上一篇:DIV+CSS 规范命名集合


下一篇:Hadoop之HDFS原理及文件上传下载源码分析(上)